WebSVN – HelenOS – Blame – /branches/rcu/kernel/test/timeout/timeoutbench1.c

Rev	Author	Line No.	Line
2431	mencl	1	/*
		2	* Copyright (c) 2007 Vojtech Mencl
		3	* All rights reserved.
		4	*
		5	* Redistribution and use in source and binary forms, with or without
		6	* modification, are permitted provided that the following conditions
		7	* are met:
		8	*
		9	* - Redistributions of source code must retain the above copyright
		10	* notice, this list of conditions and the following disclaimer.
		11	* - Redistributions in binary form must reproduce the above copyright
		12	* notice, this list of conditions and the following disclaimer in the
		13	* documentation and/or other materials provided with the distribution.
		14	* - The name of the author may not be used to endorse or promote products
		15	* derived from this software without specific prior written permission.
		16	*
		17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
		18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
		19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
		20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
		21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
		22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
		23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
		24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
		25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
		26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		27	*/
		28
		29	#include <test.h>
		30	#include <print.h>
		31	#include <adt/avl.h>
2461	mencl	32	#include <adt/favl.h>
2431	mencl	33	#include <adt/extavl.h>
		34	#include <adt/extavlrel.h>
		35	#include <debug.h>
		36	#include <arch/types.h>
		37	#include <arch/cycle.h>
		38	#include <arch/asm.h>
		39	#include <panic.h>
		40	#include <mm/slab.h>
		41
		42	/*
		43	* Node count must be more then 1000!
		44	*/
2450	mencl	45	#define NODE_COUNT 100000
2431	mencl	46	#define GEN_NUM 275604541
2450	mencl	47	#define OPERATION_COUNT 1000000
2431	mencl	48	#define TEST_COUNT 3
		49
		50	static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT};
		51
		52	/*
		53	* Wrapper tree data structures.
		54	*/
		55	static avltree_t avltree;
2461	mencl	56	static favltree_t favltree;
2431	mencl	57	static extavltree_t extavltree;
		58	static extavlreltree_t extavlreltree;
		59
		60	/*
		61	* Slab cache variables.
		62	*/
		63	static slab_cache_t *avl_slab;
2461	mencl	64	static slab_cache_t *favl_slab;
2431	mencl	65	static slab_cache_t *extavl_slab;
		66	static slab_cache_t *extavlrel_slab;
		67
		68	/*
		69	* Head of free nodes' list:
		70	*/
		71	static avltree_node_t *avl_ffn = NULL;
2461	mencl	72	static favltree_node_t *favl_ffn = NULL;
2431	mencl	73	static extavltree_node_t *extavl_ffn = NULL;
		74	static extavlreltree_node_t *extavlrel_ffn = NULL;
		75
		76
		77	static void keys_prepare(int node_count, int type)
		78	{
		79	unsigned int i;
		80	uint16_t s;
		81	avltree_node_t *a = avl_ffn;
2461	mencl	82	favltree_node_t *b = favl_ffn;
		83	extavltree_node_t *c = extavl_ffn;
		84	extavlreltree_node_t *d = extavlrel_ffn;
2431	mencl	85
		86	switch (type) {
		87	case 0:
		88	s = (uint16_t) get_cycle();
		89	for (i = 0; i < node_count; i++) {
		90	a->key = s;
		91	b->key = s;
		92	c->key = s;
2461	mencl	93	d->key = s;
2431	mencl	94	s += GEN_NUM;
		95	a = a->par;
		96	b = b->par;
		97	c = c->par;
2461	mencl	98	d = d->par;
2431	mencl	99	}
		100	break;
		101	case 1:
		102	for (i = 1; i <= node_count; i++) {
		103	a->key = i;
		104	b->key = i;
		105	c->key = i;
2461	mencl	106	d->key = i;
2431	mencl	107	a = a->par;
		108	b = b->par;
		109	c = c->par;
2461	mencl	110	d = d->par;
2431	mencl	111	}
		112	break;
		113	case 2:
		114	for (i = node_count; i > 0; i--) {
		115	a->key = i;
		116	b->key = i;
		117	c->key = i;
2461	mencl	118	d->key = i;
2431	mencl	119	a = a->par;
		120	b = b->par;
2461	mencl	121	c = c->par;
		122	d = d->par;
2431	mencl	123	}
		124	break;
		125	}
		126	}
		127
		128
		129	static bool alloc_nodes(int node_count)
		130	{
		131	int i;
		132	avltree_node_t *a;
		133	extavltree_node_t *b;
		134	extavlreltree_node_t *c;
2461	mencl	135	favltree_node_t *d;
2431	mencl	136
		137	avl_ffn = NULL;
2461	mencl	138	favl_ffn = NULL;
2431	mencl	139	extavl_ffn = NULL;
		140	extavlrel_ffn = NULL;
		141
		142	for (i = 0; i < node_count; i++) {
		143	a = (avltree_node_t *) slab_alloc(avl_slab,0);
		144	if (!a) {
		145	printf("Not enough memory to allocate test arrays.");
		146	return false;
		147	}
		148	b = (extavltree_node_t *) slab_alloc(extavl_slab,0);
		149	if (!b) {
		150	printf("Not enough memory to allocate test arrays.");
		151	return false;
		152	}
		153	c = (extavlreltree_node_t *) slab_alloc(extavlrel_slab,0);
		154	if (!c) {
		155	printf("Not enough memory to allocate test arrays.");
		156	return false;
		157	}
2461	mencl	158	d = (favltree_node_t *) slab_alloc(favl_slab,0);
		159	if (!d) {
		160	printf("Not enough memory to allocate test arrays.");
		161	return false;
		162	}
2431	mencl	163	a->par = avl_ffn;
		164	b->par = extavl_ffn;
		165	c->par = extavlrel_ffn;
2461	mencl	166	d->par = favl_ffn;
2431	mencl	167	avl_ffn = a;
		168	extavl_ffn = b;
		169	extavlrel_ffn = c;
2461	mencl	170	favl_ffn = d;
2431	mencl	171	}
		172	return true;
		173	}
		174
		175	static void free_nodes(int node_count)
		176	{
		177	int i;
		178	avltree_node_t *a;
		179	extavltree_node_t *b;
		180	extavlreltree_node_t *c;
2461	mencl	181	favltree_node_t *d;
2431	mencl	182
		183	for (i = 0; i < node_count; i++) {
		184	a = avl_ffn;
		185	b = extavl_ffn;
		186	c = extavlrel_ffn;
2461	mencl	187	d = favl_ffn;
		188	if (!a \|\| !b \|\| !c \|\| !d) {
		189	printf("Deleted nodes: %d, node count: %d, a: %p, b: %p, c: %p, d: %p\n",
		190	i,node_count,a,b,c,d);
2431	mencl	191	panic("Some nodes have been lost!");
		192	}
		193	avl_ffn = avl_ffn->par;
		194	extavl_ffn = extavl_ffn->par;
		195	extavlrel_ffn = extavlrel_ffn->par;
2461	mencl	196	favl_ffn = favl_ffn->par;
2431	mencl	197	slab_free(avl_slab,a);
		198	slab_free(extavl_slab,b);
		199	slab_free(extavlrel_slab,c);
2461	mencl	200	slab_free(favl_slab,d);
2431	mencl	201	}
		202	}
		203
		204	static avltree_node_t *alloc_avltree_node(void)
		205	{
		206	avltree_node_t *node;
		207
		208	node = avl_ffn;
		209	avl_ffn = avl_ffn->par;
		210
		211	return node;
		212	}
		213
2461	mencl	214	static favltree_node_t *alloc_favltree_node(void)
		215	{
		216	favltree_node_t *node;
		217
		218	node = favl_ffn;
		219	favl_ffn = favl_ffn->par;
		220
		221	return node;
		222	}
		223
2431	mencl	224	static extavltree_node_t *alloc_extavltree_node(void)
		225	{
		226	extavltree_node_t *node;
		227
		228	node = extavl_ffn;
		229
		230	extavl_ffn = extavl_ffn->par;
		231
		232	return node;
		233	}
		234
		235	static extavlreltree_node_t *alloc_extavlreltree_node(void)
		236	{
		237	extavlreltree_node_t *node;
		238
		239	node = extavlrel_ffn;
		240	extavlrel_ffn = extavlrel_ffn->par;
		241
		242	return node;
		243	}
		244
		245	static void free_avltree_node(avltree_node_t *node)
		246	{
		247	node->par = avl_ffn;
		248	avl_ffn = node;
		249	}
		250
2461	mencl	251	static void free_favltree_node(favltree_node_t *node)
		252	{
		253	node->par = favl_ffn;
		254	favl_ffn = node;
		255	}
		256
2431	mencl	257	static void free_extavltree_node(extavltree_node_t *node)
		258	{
		259	node->par = extavl_ffn;
		260	extavl_ffn = node;
		261	}
		262
		263	static void free_extavlreltree_node(extavlreltree_node_t *node)
		264	{
		265	node->par = extavlrel_ffn;
		266	extavlrel_ffn = node;
		267	}
		268
		269	/** Insert keys of ascending sequence and delete tree deleting root nodes.
		270	*/
		271	static void test1(void)
		272	{
2461	mencl	273	uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
		274	uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
2431	mencl	275	unsigned int i,ii;
		276	avltree_node_t *a;
		277	extavltree_node_t *b;
		278	extavlreltree_node_t *c;
2461	mencl	279	favltree_node_t *d;
2431	mencl	280
		281
		282	printf("INSERT nodes with keys of ascending sequence.\n");
		283	printf("Nodes:\t\t");
		284	for (ii = 0; ii < TEST_COUNT; ii++) {
		285	printf("%20u",node_count[ii]);
		286	keys_prepare(node_count[ii],1);
		287
		288	/*
		289	* AVL INSERT
		290	*/
		291	s[0][ii] = get_cycle();
		292
		293	avltree_create(&avltree);
		294	for (i = 0; i < node_count[ii]; i++) {
		295	avltree_insert(&avltree,alloc_avltree_node());
		296	}
		297
		298	f[0][ii] = get_cycle();
		299	/*
		300	* AVL DELETE
		301	*/
		302	ds[0][ii] = get_cycle();
		303
		304	while ((a = avltree.root) != NULL) {
		305	avltree_delete(&avltree,a);
		306	free_avltree_node(a);
		307	}
		308
		309	df[0][ii] = get_cycle();
		310
		311	/*
		312	* ExtAVL INSERT
		313	*/
		314	s[1][ii] = get_cycle();
		315
		316	extavltree_create(&extavltree);
		317	for (i = 0; i < node_count[ii]; i++) {
		318	extavltree_insert(&extavltree,alloc_extavltree_node());
		319	}
		320
		321	f[1][ii] = get_cycle();
		322	/*
		323	* ExtAVL DELETE
		324	*/
		325	ds[1][ii] = get_cycle();
		326
		327	while ((b = extavltree.root) != NULL) {
		328	extavltree_delete(&extavltree,b);
		329	free_extavltree_node(b);
		330	}
		331
		332	df[1][ii] = get_cycle();
		333
		334	/*
		335	* ExtAVLrel INSERT
		336	*/
		337	s[2][ii] = get_cycle();
		338
		339	extavlreltree_create(&extavlreltree);
		340	for (i = 0; i < node_count[ii]; i++) {
		341	extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
		342	}
		343
		344	f[2][ii] = get_cycle();
		345	/*
		346	* ExtAVLrel DELETE
		347	*/
		348	ds[2][ii] = get_cycle();
		349
		350	while ((c = extavlreltree.root) != NULL) {
		351	extavlreltree_delete(&extavlreltree,c);
		352	free_extavlreltree_node(c);
		353	}
		354
		355	df[2][ii] = get_cycle();
2461	mencl	356
		357	/*
		358	* FAVL INSERT
		359	*/
		360	s[3][ii] = get_cycle();
		361
		362	favltree_create(&favltree);
		363	for (i = 0; i < node_count[ii]; i++) {
		364	favltree_insert(&favltree,alloc_favltree_node());
		365	}
		366
		367	f[3][ii] = get_cycle();
		368	/*
		369	* FAVL DELETE
		370	*/
		371	ds[3][ii] = get_cycle();
		372
		373	while ((d = favltree.root) != NULL) {
		374	favltree_delete(&favltree,d);
		375	free_favltree_node(d);
		376	}
		377
		378	df[3][ii] = get_cycle();
2431	mencl	379	}
		380	printf("\n----------------------------------------------------------------------------");
		381	printf("\nAVL\t\t");
		382	for (ii = 0; ii < TEST_COUNT; ii++)
		383	printf("%20llu",f[0][ii]-s[0][ii]);
2461	mencl	384	printf("\nFAVL\t\t");
		385	for (ii = 0; ii < TEST_COUNT; ii++)
		386	printf("%20llu",f[3][ii]-s[3][ii]);
2431	mencl	387	printf("\nExtAVL\t\t");
		388	for (ii = 0; ii < TEST_COUNT; ii++)
		389	printf("%20llu",f[1][ii]-s[1][ii]);
		390	printf("\nExtAVLrel\t");
		391	for (ii = 0; ii < TEST_COUNT; ii++)
		392	printf("%20llu",f[2][ii]-s[2][ii]);
		393	printf("\n\n");
		394
		395	printf("DELETE tree deleting root nodes\n");
		396	printf("Nodes:\t\t");
		397	for (ii = 0; ii < TEST_COUNT; ii++)
		398	printf("%20u",node_count[ii]);
		399	printf("\n----------------------------------------------------------------------------");
		400	printf("\nAVL\t\t");
		401	for (ii = 0; ii < TEST_COUNT; ii++)
		402	printf("%20llu",df[0][ii]-ds[0][ii]);
2461	mencl	403	printf("\nAVL\t\t");
		404	for (ii = 0; ii < TEST_COUNT; ii++)
		405	printf("%20llu",df[3][ii]-ds[3][ii]);
2431	mencl	406	printf("\nExtAVL\t\t");
		407	for (ii = 0; ii < TEST_COUNT; ii++)
		408	printf("%20llu",df[1][ii]-ds[1][ii]);
		409	printf("\nExtAVLrel\t");
		410	for (ii = 0; ii < TEST_COUNT; ii++)
		411	printf("%20llu",df[2][ii]-ds[2][ii]);
		412	printf("\n\n");
		413	}
		414
		415
		416	/** Insert keys of ascending sequence and delete tree with delete_min functions.
		417	*/
		418	static void test2(void)
		419	{
2461	mencl	420	uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
		421	uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
2431	mencl	422	unsigned int i,ii;
		423	avltree_node_t *a;
		424	extavltree_node_t *b;
		425	extavlreltree_node_t *c;
2461	mencl	426	favltree_node_t *d;
2431	mencl	427
		428
		429	printf("INSERT nodes with keys of descending sequence.\n");
		430	printf("Nodes:\t\t");
		431	for (ii = 0; ii < TEST_COUNT; ii++) {
		432	printf("%20u",node_count[ii]);
		433	keys_prepare(node_count[ii],2);
		434
		435	/*
		436	* AVL INSERT
		437	*/
		438	s[0][ii] = get_cycle();
		439
		440	avltree_create(&avltree);
		441	for (i = 0; i < node_count[ii]; i++) {
		442	avltree_insert(&avltree,alloc_avltree_node());
		443	}
		444
		445	f[0][ii] = get_cycle();
		446	/*
		447	* AVL DELETE
		448	*/
		449	ds[0][ii] = get_cycle();
		450
		451	while (avltree.root != NULL) {
		452	a = avltree_find_min(&avltree);
		453	avltree_delete_min(&avltree);
		454	free_avltree_node(a);
		455	}
		456
		457	df[0][ii] = get_cycle();
		458
		459	/*
		460	* ExtAVL INSERT
		461	*/
		462	s[1][ii] = get_cycle();
		463
		464	extavltree_create(&extavltree);
		465	for (i = 0; i < node_count[ii]; i++) {
		466	extavltree_insert(&extavltree,alloc_extavltree_node());
		467	}
		468
		469	f[1][ii] = get_cycle();
		470	/*
		471	* ExtAVL DELETE
		472	*/
		473	ds[1][ii] = get_cycle();
		474
		475	while (extavltree.root != NULL) {
		476	b = extavltree.head.next;
		477	extavltree_delete_min(&extavltree);
		478	free_extavltree_node(b);
		479	}
		480
		481	df[1][ii] = get_cycle();
		482	/*
		483	* ExtAVLrel INSERT
		484	*/
		485	s[2][ii] = get_cycle();
		486
		487	extavlreltree_create(&extavlreltree);
		488	for (i = 0; i < node_count[ii]; i++) {
		489	extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
		490	}
		491
		492	f[2][ii] = get_cycle();
		493	/*
		494	* ExtAVLrel DELETE
		495	*/
		496	ds[2][ii] = get_cycle();
		497
		498	while (extavlreltree.root != NULL) {
		499	c = extavlreltree.head.next;
		500	extavlreltree_delete_min(&extavlreltree);
		501	free_extavlreltree_node(c);
		502	}
		503
		504	df[2][ii] = get_cycle();
2461	mencl	505
		506	/*
		507	* FAVL INSERT
		508	*/
		509	s[3][ii] = get_cycle();
		510
		511	favltree_create(&favltree);
		512	for (i = 0; i < node_count[ii]; i++) {
		513	favltree_insert(&favltree,alloc_favltree_node());
		514	}
		515
		516	f[3][ii] = get_cycle();
		517	/*
		518	* AVL DELETE
		519	*/
		520	ds[3][ii] = get_cycle();
		521
		522	while (favltree.root != NULL) {
		523	d = favltree_find_min(&favltree);
		524	favltree_delete_min(&favltree);
		525	free_favltree_node(d);
		526	}
		527
		528	df[3][ii] = get_cycle();
		529
2431	mencl	530	}
		531	printf("\n----------------------------------------------------------------------------");
		532	printf("\nAVL\t\t");
		533	for (ii = 0; ii < TEST_COUNT; ii++)
		534	printf("%20llu",f[0][ii]-s[0][ii]);
2461	mencl	535	printf("\nFAVL\t\t");
		536	for (ii = 0; ii < TEST_COUNT; ii++)
		537	printf("%20llu",f[3][ii]-s[3][ii]);
2431	mencl	538	printf("\nExtAVL\t\t");
		539	for (ii = 0; ii < TEST_COUNT; ii++)
		540	printf("%20llu",f[1][ii]-s[1][ii]);
		541	printf("\nExtAVLrel\t");
		542	for (ii = 0; ii < TEST_COUNT; ii++)
		543	printf("%20llu",f[2][ii]-s[2][ii]);
		544	printf("\n\n");
		545
		546	printf("DELETE tree deleting nodes with minimal key\n");
		547	printf("Nodes:\t\t");
		548	for (ii = 0; ii < TEST_COUNT; ii++)
		549	printf("%20u",node_count[ii]);
		550	printf("\n----------------------------------------------------------------------------");
		551	printf("\nAVL\t\t");
		552	for (ii = 0; ii < TEST_COUNT; ii++)
		553	printf("%20llu",df[0][ii]-ds[0][ii]);
2461	mencl	554	printf("\nFAVL\t\t");
		555	for (ii = 0; ii < TEST_COUNT; ii++)
		556	printf("%20llu",df[3][ii]-ds[3][ii]);
2431	mencl	557	printf("\nExtAVL\t\t");
		558	for (ii = 0; ii < TEST_COUNT; ii++)
		559	printf("%20llu",df[1][ii]-ds[1][ii]);
		560	printf("\nExtAVLrel\t");
		561	for (ii = 0; ii < TEST_COUNT; ii++)
		562	printf("%20llu",df[2][ii]-ds[2][ii]);
		563	printf("\n\n");
		564	}
		565
		566
		567	/** Insert keys of random sequence and delete tree with delete_min functions.
		568	*/
		569	static void test3(void)
		570	{
2461	mencl	571	uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
		572	uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
2431	mencl	573	unsigned int i,ii;
		574	avltree_node_t *a;
		575	extavltree_node_t *b;
		576	extavlreltree_node_t *c;
2461	mencl	577	favltree_node_t *d;
2431	mencl	578
		579
		580	printf("INSERT nodes with keys of random sequence 1-65536.\n");
		581	printf("Nodes:\t\t");
		582	for (ii = 0; ii < TEST_COUNT; ii++) {
		583	printf("%20u",node_count[ii]);
		584	keys_prepare(node_count[ii],0);
		585
		586	/*
		587	* AVL INSERT
		588	*/
		589	s[0][ii] = get_cycle();
		590
		591	avltree_create(&avltree);
		592	for (i = 0; i < node_count[ii]; i++) {
		593	avltree_insert(&avltree,alloc_avltree_node());
		594	}
		595
		596	f[0][ii] = get_cycle();
		597	/*
		598	* AVL DELETE
		599	*/
		600	ds[0][ii] = get_cycle();
		601
		602	while (avltree.root != NULL) {
		603	a = avltree_find_min(&avltree);
		604	avltree_delete_min(&avltree);
		605	free_avltree_node(a);
		606	}
		607
		608	df[0][ii] = get_cycle();
		609
		610	/*
		611	* ExtAVL INSERT
		612	*/
		613	s[1][ii] = get_cycle();
		614
		615	extavltree_create(&extavltree);
		616	for (i = 0; i < node_count[ii]; i++) {
		617	extavltree_insert(&extavltree,alloc_extavltree_node());
		618	}
		619
		620	f[1][ii] = get_cycle();
		621	/*
		622	* ExtAVL DELETE
		623	*/
		624	ds[1][ii] = get_cycle();
		625
		626	while (extavltree.root != NULL) {
		627	b = extavltree.head.next;
		628	extavltree_delete_min(&extavltree);
		629	free_extavltree_node(b);
		630	}
		631
		632	df[1][ii] = get_cycle();
		633	/*
		634	* ExtAVLrel INSERT
		635	*/
		636	s[2][ii] = get_cycle();
		637
		638	extavlreltree_create(&extavlreltree);
		639	for (i = 0; i < node_count[ii]; i++) {
		640	extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
		641	}
		642
		643	f[2][ii] = get_cycle();
		644	/*
		645	* ExtAVLrel DELETE
		646	*/
		647	ds[2][ii] = get_cycle();
		648
		649	while (extavlreltree.root != NULL) {
		650	c = extavlreltree.head.next;
		651	extavlreltree_delete_min(&extavlreltree);
		652	free_extavlreltree_node(c);
		653	}
		654
		655	df[2][ii] = get_cycle();
2461	mencl	656
		657	/*
		658	* FAVL INSERT
		659	*/
		660	s[3][ii] = get_cycle();
		661
		662	favltree_create(&favltree);
		663	for (i = 0; i < node_count[ii]; i++) {
		664	favltree_insert(&favltree,alloc_favltree_node());
		665	}
		666
		667	f[3][ii] = get_cycle();
		668	/*
		669	* AVL DELETE
		670	*/
		671	ds[3][ii] = get_cycle();
		672
		673	while (favltree.root != NULL) {
		674	d = favltree_find_min(&favltree);
		675	favltree_delete_min(&favltree);
		676	free_favltree_node(d);
		677	}
		678
		679	df[3][ii] = get_cycle();
2431	mencl	680	}
		681	printf("\n----------------------------------------------------------------------------");
		682	printf("\nAVL\t\t");
		683	for (ii = 0; ii < TEST_COUNT; ii++)
		684	printf("%20llu",f[0][ii]-s[0][ii]);
2461	mencl	685	printf("\nFAVL\t\t");
		686	for (ii = 0; ii < TEST_COUNT; ii++)
		687	printf("%20llu",f[3][ii]-s[3][ii]);
2431	mencl	688	printf("\nExtAVL\t\t");
		689	for (ii = 0; ii < TEST_COUNT; ii++)
		690	printf("%20llu",f[1][ii]-s[1][ii]);
		691	printf("\nExtAVLrel\t");
		692	for (ii = 0; ii < TEST_COUNT; ii++)
		693	printf("%20llu",f[2][ii]-s[2][ii]);
		694	printf("\n\n");
		695
		696	printf("DELETE tree deleting nodes with minimal key\n");
		697	printf("Nodes:\t\t");
		698	for (ii = 0; ii < TEST_COUNT; ii++)
		699	printf("%20u",node_count[ii]);
		700	printf("\n----------------------------------------------------------------------------");
		701	printf("\nAVL\t\t");
		702	for (ii = 0; ii < TEST_COUNT; ii++)
		703	printf("%20llu",df[0][ii]-ds[0][ii]);
2461	mencl	704	printf("\nFAVL\t\t");
		705	for (ii = 0; ii < TEST_COUNT; ii++)
		706	printf("%20llu",df[3][ii]-ds[3][ii]);
2431	mencl	707	printf("\nExtAVL\t\t");
		708	for (ii = 0; ii < TEST_COUNT; ii++)
		709	printf("%20llu",df[1][ii]-ds[1][ii]);
		710	printf("\nExtAVLrel\t");
		711	for (ii = 0; ii < TEST_COUNT; ii++)
		712	printf("%20llu",df[2][ii]-ds[2][ii]);
		713	printf("\n\n");
		714	}
		715
		716
		717	/** Simulating timeout mechanismus with insert and delete_min operations.
		718	*/
		719	static void test4(void)
		720	{
2461	mencl	721	uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
2431	mencl	722	unsigned int i,ii;
		723	avltree_node_t *a;
		724	extavltree_node_t *b;
		725	extavlreltree_node_t *c;
2461	mencl	726	favltree_node_t *d;
2431	mencl	727	uint64_t r;
		728	uint16_t rr;
		729	unsigned int mn,nc;
		730
		731
		732	printf("Simulating timeout mechanismus with %d insert or delete_min operations\n",OPERATION_COUNT);
		733	printf("Maximum nodes:\t");
		734	for (ii = 0; ii < TEST_COUNT; ii++) {
		735	printf("%20u",node_count[ii]);
		736
		737	r = (uint64_t) get_cycle();
		738	mn = node_count[ii];
		739
		740	/*
		741	* AVL
		742	*/
		743	rr = r;
		744	nc = 0;
		745	s[0][ii] = get_cycle();
		746
		747	avltree_create(&avltree);
		748	for (i = 0; i < OPERATION_COUNT; i++) {
		749	if (((rr % mn) <= nc) && nc) {
		750	/*
		751	* Delete min.
		752	*/
		753	a = avltree_find_min(&avltree);
		754	avltree_delete_min(&avltree);
		755	free_avltree_node(a);
		756	nc--;
		757	} else {
		758	/*
		759	* Insert.
		760	*/
		761	a = alloc_avltree_node();
		762	a->key = rr;
		763	avltree_insert(&avltree,a);
		764	nc++;
		765	}
		766	rr += GEN_NUM;
		767	}
		768	/*
		769	* Delete rest tree.
		770	*/
		771	while (avltree.root != NULL) {
		772	a = avltree_find_min(&avltree);
		773	avltree_delete_min(&avltree);
		774	free_avltree_node(a);
		775	}
		776
		777	f[0][ii] = get_cycle();
		778
		779	/*
2461	mencl	780	* FAVL
		781	*/
		782	rr = r;
		783	nc = 0;
		784	s[3][ii] = get_cycle();
		785
		786	avltree_create(&avltree);
		787	for (i = 0; i < OPERATION_COUNT; i++) {
		788	if (((rr % mn) <= nc) && nc) {
		789	/*
		790	* Delete min.
		791	*/
		792	d = favltree_find_min(&favltree);
		793	favltree_delete_min(&favltree);
		794	free_favltree_node(d);
		795	nc--;
		796	} else {
		797	/*
		798	* Insert.
		799	*/
		800	d = alloc_favltree_node();
		801	d->key = rr;
		802	favltree_insert(&favltree,d);
		803	nc++;
		804	}
		805	rr += GEN_NUM;
		806	}
		807	/*
		808	* Delete rest tree.
		809	*/
		810	while (favltree.root != NULL) {
		811	d = favltree_find_min(&favltree);
		812	favltree_delete_min(&favltree);
		813	free_favltree_node(d);
		814	}
		815
		816	f[3][ii] = get_cycle();
		817
		818	/*
2431	mencl	819	* ExtAVL
		820	*/
		821	rr = r;
		822	nc = 0;
		823	s[1][ii] = get_cycle();
		824
		825	extavltree_create(&extavltree);
		826	for (i = 0; i < OPERATION_COUNT; i++) {
		827	if (((rr % mn) <= nc) && nc) {
		828	/*
		829	* Delete min.
		830	*/
		831	b = extavltree.head.next;
		832	extavltree_delete_min(&extavltree);
		833	free_extavltree_node(b);
		834	nc--;
		835	} else {
		836	/*
		837	* Insert.
		838	*/
		839	b = alloc_extavltree_node();
		840	b->key = rr;
		841	extavltree_insert(&extavltree,b);
		842	nc++;
		843	}
		844	rr += GEN_NUM;
		845	}
		846	/*
		847	* Delete rest tree.
		848	*/
		849	while (extavltree.root != NULL) {
		850	b = extavltree.head.next;
		851	extavltree_delete_min(&extavltree);
		852	free_extavltree_node(b);
		853	}
		854
		855	f[1][ii] = get_cycle();
		856
		857	/*
		858	* ExtAVLrel
		859	*/
		860	rr = r;
		861	nc = 0;
		862	s[2][ii] = get_cycle();
		863
		864	extavlreltree_create(&extavlreltree);
		865	for (i = 0; i < OPERATION_COUNT; i++) {
		866	if (((rr % mn) <= nc) && nc) {
		867	/*
		868	* Delete min.
		869	*/
		870	c = extavlreltree.head.next;
		871	//if (ii == 2 && !(i % 100)) printf("DEL key %llu, nc: %u, op: %u\n",c->key,nc,i);
		872	extavlreltree_delete_min(&extavlreltree);
		873	free_extavlreltree_node(c);
		874	nc--;
		875	} else {
		876	/*
		877	* Insert.
		878	*/
		879	c = alloc_extavlreltree_node();
		880	c->key = rr;
		881	//if (ii == 2 && !(i % 100)) printf("INS key %llu, nc: %u, op: %u\n",c->key,nc,i);
		882	extavlreltree_insert(&extavlreltree,c);
		883	nc++;
		884	}
		885	rr += GEN_NUM;
		886	}
		887	/*
		888	* Delete rest tree.
		889	*/
		890	while (extavlreltree.root != NULL) {
		891	c = extavlreltree.head.next;
		892	extavlreltree_delete_min(&extavlreltree);
		893	free_extavlreltree_node(c);
		894	}
		895
		896	f[2][ii] = get_cycle();
		897	}
		898	printf("\n----------------------------------------------------------------------------");
		899	printf("\nAVL\t\t");
		900	for (ii = 0; ii < TEST_COUNT; ii++)
		901	printf("%20llu",f[0][ii]-s[0][ii]);
2461	mencl	902	printf("\nFAVL\t\t");
		903	for (ii = 0; ii < TEST_COUNT; ii++)
		904	printf("%20llu",f[3][ii]-s[3][ii]);
2431	mencl	905	printf("\nExtAVL\t\t");
		906	for (ii = 0; ii < TEST_COUNT; ii++)
		907	printf("%20llu",f[1][ii]-s[1][ii]);
		908	printf("\nExtAVLrel\t");
		909	for (ii = 0; ii < TEST_COUNT; ii++)
		910	printf("%20llu",f[2][ii]-s[2][ii]);
		911	printf("\n\n");
		912	}
		913
		914
		915	char * test_timeoutbench1(bool quiet)
		916	{
		917	printf("\n\tBenchmark test of timeout data structures: AVL, ExtAVL and ExtAVLrel.\n"
		918	"Run test more than once for eliminating possible distortion due to caching!\n\n");
		919
		920
		921	avl_slab = slab_cache_create("avl_slab",sizeof(avltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
2461	mencl	922	favl_slab = slab_cache_create("favl_slab",sizeof(favltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
2431	mencl	923	extavl_slab = slab_cache_create("extavl_slab",sizeof(extavltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
		924	extavlrel_slab = slab_cache_create("extavlrel_slab",sizeof(extavlreltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
		925
		926	if (!alloc_nodes(NODE_COUNT))
		927	return NULL;
		928
		929	/*
		930	* store initial cycle count,
		931	* do test,
		932	* store finish cycle count,
		933	* show results
		934	*/
		935
		936	test1();
		937	test2();
		938	test3();
		939	test4();
		940
		941	/*
		942	* Deallocate arrays.
		943	*/
		944	free_nodes(NODE_COUNT);
		945
		946	return NULL;
		947	}

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/timeout/timeoutbench1.c – Rev 2461