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

Subversion Repositories HelenOS

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