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



#include <mm/slab.h>
 
/*
 * Node count must be more then 1000!
 */
#define NODE_COUNT 100000
#define GEN_NUM 275604541
#define OPERATION_COUNT 1000000
#define TEST_COUNT 3
 
static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT};
 
/*

 
/** Insert keys of ascending sequence and delete tree deleting root nodes.
 */
static void test1(void)
{
 
    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
    uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
    unsigned int i,ii;
    avltree_node_t *a;
    extavltree_node_t *b;

        keys_prepare(node_count[ii],1);
 
        /*
         * AVL INSERT
         */
 
        s[0][ii] = get_cycle();
       
        avltree_create(&avltree);
        for (i = 0; i < node_count[ii]; i++) {
            avltree_insert(&avltree,alloc_avltree_node());
        }
           
        f[0][ii] = get_cycle();
 
        /*
         * AVL DELETE
         */
 
        ds[0][ii] = get_cycle();
       
        while ((a = avltree.root) != NULL) {
            avltree_delete(&avltree,a);
            free_avltree_node(a);
        }
           
        df[0][ii] = get_cycle();
 
 
        /*
         * ExtAVL INSERT
         */
 
        s[1][ii] = get_cycle();
       
        extavltree_create(&extavltree);
        for (i = 0; i < node_count[ii]; i++) {
            extavltree_insert(&extavltree,alloc_extavltree_node());
        }
       
        f[1][ii] = get_cycle();
 
        /*
         * ExtAVL DELETE
         */
 
        ds[1][ii] = get_cycle();
       
        while ((b = extavltree.root) != NULL) {
            extavltree_delete(&extavltree,b);
            free_extavltree_node(b);
        }
           
        df[1][ii] = get_cycle();
 
 
        /*
         * ExtAVLrel INSERT
         */
 
        s[2][ii] = get_cycle();
       
        extavlreltree_create(&extavlreltree);
        for (i = 0; i < node_count[ii]; i++) {
            extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
        }
       
        f[2][ii] = get_cycle();
 
        /*
         * ExtAVLrel DELETE
         */
 
        ds[2][ii] = get_cycle();
       
        while ((c = extavlreltree.root) != NULL) {
            extavlreltree_delete(&extavlreltree,c);
            free_extavlreltree_node(c);
        }
           
        df[2][ii] = get_cycle();
 
    }
    printf("\n----------------------------------------------------------------------------");  
    printf("\nAVL\t\t");
    for (ii = 0; ii < TEST_COUNT; ii++)
        printf("%20llu",f[0][ii]-s[0][ii]);

 
/** Insert keys of ascending sequence and delete tree with delete_min functions.
 */
static void test2(void)
{
 
    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
    uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
    unsigned int i,ii;
    avltree_node_t *a;
    extavltree_node_t *b;

        keys_prepare(node_count[ii],2);
       
        /*
         * AVL INSERT
         */
 
        s[0][ii] = get_cycle();
       
        avltree_create(&avltree);
        for (i = 0; i < node_count[ii]; i++) {
            avltree_insert(&avltree,alloc_avltree_node());
        }
           
        f[0][ii] = get_cycle();
 
        /*
         * AVL DELETE
         */
 
        ds[0][ii] = get_cycle();
       
        while (avltree.root != NULL) {
            a = avltree_find_min(&avltree);
            avltree_delete_min(&avltree);
            free_avltree_node(a);
        }
           
        df[0][ii] = get_cycle();
 
 
        /*
         * ExtAVL INSERT
         */
 
        s[1][ii] = get_cycle();
       
        extavltree_create(&extavltree);
        for (i = 0; i < node_count[ii]; i++) {
            extavltree_insert(&extavltree,alloc_extavltree_node());
        }
       
        f[1][ii] = get_cycle();
 
        /*
         * ExtAVL DELETE
         */
 
        ds[1][ii] = get_cycle();
       
        while (extavltree.root != NULL) {
            b = extavltree.head.next;
            extavltree_delete_min(&extavltree);
            free_extavltree_node(b);
        }
           
        df[1][ii] = get_cycle();
 
        /*
         * ExtAVLrel INSERT
         */
 
        s[2][ii] = get_cycle();
       
        extavlreltree_create(&extavlreltree);
        for (i = 0; i < node_count[ii]; i++) {
            extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
        }
       
        f[2][ii] = get_cycle();
 
        /*
         * ExtAVLrel DELETE
         */
 
        ds[2][ii] = get_cycle();
       
        while (extavlreltree.root != NULL) {
            c = extavlreltree.head.next;
            extavlreltree_delete_min(&extavlreltree);
            free_extavlreltree_node(c);
        }
           
        df[2][ii] = get_cycle();
 
    }
    printf("\n----------------------------------------------------------------------------");  
    printf("\nAVL\t\t");
    for (ii = 0; ii < TEST_COUNT; ii++)
        printf("%20llu",f[0][ii]-s[0][ii]);

 
/** Insert keys of random sequence and delete tree with delete_min functions.
 */
static void test3(void)
{
 
    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
    uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
    unsigned int i,ii;
    avltree_node_t *a;
    extavltree_node_t *b;

        keys_prepare(node_count[ii],0);
       
        /*
         * AVL INSERT
         */
 
        s[0][ii] = get_cycle();
       
        avltree_create(&avltree);
        for (i = 0; i < node_count[ii]; i++) {
            avltree_insert(&avltree,alloc_avltree_node());
        }
           
        f[0][ii] = get_cycle();
 
        /*
         * AVL DELETE
         */
 
        ds[0][ii] = get_cycle();
       
        while (avltree.root != NULL) {
            a = avltree_find_min(&avltree);
            avltree_delete_min(&avltree);
            free_avltree_node(a);
        }
           
        df[0][ii] = get_cycle();
 
 
        /*
         * ExtAVL INSERT
         */
 
        s[1][ii] = get_cycle();
       
        extavltree_create(&extavltree);
        for (i = 0; i < node_count[ii]; i++) {
            extavltree_insert(&extavltree,alloc_extavltree_node());
        }
       
        f[1][ii] = get_cycle();
 
        /*
         * ExtAVL DELETE
         */
 
        ds[1][ii] = get_cycle();
       
        while (extavltree.root != NULL) {
            b = extavltree.head.next;
            extavltree_delete_min(&extavltree);
            free_extavltree_node(b);
        }
           
        df[1][ii] = get_cycle();
 
        /*
         * ExtAVLrel INSERT
         */
 
        s[2][ii] = get_cycle();
       
        extavlreltree_create(&extavlreltree);
        for (i = 0; i < node_count[ii]; i++) {
            extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
        }
       
        f[2][ii] = get_cycle();
 
        /*
         * ExtAVLrel DELETE
         */
 
        ds[2][ii] = get_cycle();
       
        while (extavlreltree.root != NULL) {
            c = extavlreltree.head.next;
            extavlreltree_delete_min(&extavlreltree);
            free_extavlreltree_node(c);
        }
           
        df[2][ii] = get_cycle();
 
    }
    printf("\n----------------------------------------------------------------------------");  
    printf("\nAVL\t\t");
    for (ii = 0; ii < TEST_COUNT; ii++)
        printf("%20llu",f[0][ii]-s[0][ii]);

 
/** Simulating timeout mechanismus with insert and delete_min operations.
 */
static void test4(void)
{
 
    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
    unsigned int i,ii;
    avltree_node_t *a;
    extavltree_node_t *b;
    extavlreltree_node_t *c;

        /*
         * AVL
         */
        rr = r;
        nc = 0;
 
        s[0][ii] = get_cycle();
       
        avltree_create(&avltree);
        for (i = 0; i < OPERATION_COUNT; i++) {
            if (((rr % mn) <= nc) && nc) {

            avltree_delete_min(&avltree);
            free_avltree_node(a);
        }  
       
        f[0][ii] = get_cycle();
 
 
        /*
         * ExtAVL
         */
        rr = r;
        nc = 0;
 
        s[1][ii] = get_cycle();
       
        extavltree_create(&extavltree);
        for (i = 0; i < OPERATION_COUNT; i++) {
            if (((rr % mn) <= nc) && nc) {

            extavltree_delete_min(&extavltree);
            free_extavltree_node(b);
        }
 
        f[1][ii] = get_cycle();
 
       
        /*
         * ExtAVLrel
         */
        rr = r;
        nc = 0;
 
        s[2][ii] = get_cycle();
       
        extavlreltree_create(&extavlreltree);
        for (i = 0; i < OPERATION_COUNT; i++) {
            if (((rr % mn) <= nc) && nc) {

            extavlreltree_delete_min(&extavlreltree);
            free_extavlreltree_node(c);
        }
 
        f[2][ii] = get_cycle();
 
    }
    printf("\n----------------------------------------------------------------------------");  
    printf("\nAVL\t\t");
    for (ii = 0; ii < TEST_COUNT; ii++)
        printf("%20llu",f[0][ii]-s[0][ii]);

 
    if (!alloc_nodes(NODE_COUNT))
        return NULL;
 
    /*
 
     * store initial cycle count,
     * do test,
     * store finish cycle count,
 
     * show results
     */
 
    test1();
    test2();

Rev 2431	Rev 2450
Line 39...	Line 39...
39	#include <mm/slab.h>	39	#include <mm/slab.h>
40		40
41	/*	41	/*
42	* Node count must be more then 1000!	42	* Node count must be more then 1000!
43	*/	43	*/
44	#define NODE_COUNT 1000000	44	#define NODE_COUNT 100000
45	#define GEN_NUM 275604541	45	#define GEN_NUM 275604541
46	#define OPERATION_COUNT 100000000	46	#define OPERATION_COUNT 1000000
47	#define TEST_COUNT 3	47	#define TEST_COUNT 3
48		48
49	static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT};	49	static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT};
50		50
51	/*	51	/*
Line 227...	Line 227...
227		227
228	/** Insert keys of ascending sequence and delete tree deleting root nodes.	228	/** Insert keys of ascending sequence and delete tree deleting root nodes.
229	*/	229	*/
230	static void test1(void)	230	static void test1(void)
231	{	231	{
232	ipl_t ipl;	-
233	uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];	232	uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
234	uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];	233	uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
235	unsigned int i,ii;	234	unsigned int i,ii;
236	avltree_node_t *a;	235	avltree_node_t *a;
237	extavltree_node_t *b;	236	extavltree_node_t *b;
Line 245...	Line 244...
245	keys_prepare(node_count[ii],1);	244	keys_prepare(node_count[ii],1);
246		245
247	/*	246	/*
248	* AVL INSERT	247	* AVL INSERT
249	*/	248	*/
250	ipl = interrupts_disable();	-
251	s[0][ii] = get_cycle();	249	s[0][ii] = get_cycle();
252		250
253	avltree_create(&avltree);	251	avltree_create(&avltree);
254	for (i = 0; i < node_count[ii]; i++) {	252	for (i = 0; i < node_count[ii]; i++) {
255	avltree_insert(&avltree,alloc_avltree_node());	253	avltree_insert(&avltree,alloc_avltree_node());
256	}	254	}
257		255
258	f[0][ii] = get_cycle();	256	f[0][ii] = get_cycle();
259	interrupts_restore(ipl);	-
260	/*	257	/*
261	* AVL DELETE	258	* AVL DELETE
262	*/	259	*/
263	ipl = interrupts_disable();	-
264	ds[0][ii] = get_cycle();	260	ds[0][ii] = get_cycle();
265		261
266	while ((a = avltree.root) != NULL) {	262	while ((a = avltree.root) != NULL) {
267	avltree_delete(&avltree,a);	263	avltree_delete(&avltree,a);
268	free_avltree_node(a);	264	free_avltree_node(a);
269	}	265	}
270		266
271	df[0][ii] = get_cycle();	267	df[0][ii] = get_cycle();
272	interrupts_restore(ipl);	-
273		268
274	/*	269	/*
275	* ExtAVL INSERT	270	* ExtAVL INSERT
276	*/	271	*/
277	ipl = interrupts_disable();	-
278	s[1][ii] = get_cycle();	272	s[1][ii] = get_cycle();
279		273
280	extavltree_create(&extavltree);	274	extavltree_create(&extavltree);
281	for (i = 0; i < node_count[ii]; i++) {	275	for (i = 0; i < node_count[ii]; i++) {
282	extavltree_insert(&extavltree,alloc_extavltree_node());	276	extavltree_insert(&extavltree,alloc_extavltree_node());
283	}	277	}
284		278
285	f[1][ii] = get_cycle();	279	f[1][ii] = get_cycle();
286	interrupts_restore(ipl);	-
287	/*	280	/*
288	* ExtAVL DELETE	281	* ExtAVL DELETE
289	*/	282	*/
290	ipl = interrupts_disable();	-
291	ds[1][ii] = get_cycle();	283	ds[1][ii] = get_cycle();
292		284
293	while ((b = extavltree.root) != NULL) {	285	while ((b = extavltree.root) != NULL) {
294	extavltree_delete(&extavltree,b);	286	extavltree_delete(&extavltree,b);
295	free_extavltree_node(b);	287	free_extavltree_node(b);
296	}	288	}
297		289
298	df[1][ii] = get_cycle();	290	df[1][ii] = get_cycle();
299	interrupts_restore(ipl);	-
300		291
301	/*	292	/*
302	* ExtAVLrel INSERT	293	* ExtAVLrel INSERT
303	*/	294	*/
304	ipl = interrupts_disable();	-
305	s[2][ii] = get_cycle();	295	s[2][ii] = get_cycle();
306		296
307	extavlreltree_create(&extavlreltree);	297	extavlreltree_create(&extavlreltree);
308	for (i = 0; i < node_count[ii]; i++) {	298	for (i = 0; i < node_count[ii]; i++) {
309	extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());	299	extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
310	}	300	}
311		301
312	f[2][ii] = get_cycle();	302	f[2][ii] = get_cycle();
313	interrupts_restore(ipl);	-
314	/*	303	/*
315	* ExtAVLrel DELETE	304	* ExtAVLrel DELETE
316	*/	305	*/
317	ipl = interrupts_disable();	-
318	ds[2][ii] = get_cycle();	306	ds[2][ii] = get_cycle();
319		307
320	while ((c = extavlreltree.root) != NULL) {	308	while ((c = extavlreltree.root) != NULL) {
321	extavlreltree_delete(&extavlreltree,c);	309	extavlreltree_delete(&extavlreltree,c);
322	free_extavlreltree_node(c);	310	free_extavlreltree_node(c);
323	}	311	}
324		312
325	df[2][ii] = get_cycle();	313	df[2][ii] = get_cycle();
326	interrupts_restore(ipl);	-
327	}	314	}
328	printf("\n----------------------------------------------------------------------------");	315	printf("\n----------------------------------------------------------------------------");
329	printf("\nAVL\t\t");	316	printf("\nAVL\t\t");
330	for (ii = 0; ii < TEST_COUNT; ii++)	317	for (ii = 0; ii < TEST_COUNT; ii++)
331	printf("%20llu",f[0][ii]-s[0][ii]);	318	printf("%20llu",f[0][ii]-s[0][ii]);
Line 357...	Line 344...
357		344
358	/** Insert keys of ascending sequence and delete tree with delete_min functions.	345	/** Insert keys of ascending sequence and delete tree with delete_min functions.
359	*/	346	*/
360	static void test2(void)	347	static void test2(void)
361	{	348	{
362	ipl_t ipl;	-
363	uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];	349	uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
364	uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];	350	uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
365	unsigned int i,ii;	351	unsigned int i,ii;
366	avltree_node_t *a;	352	avltree_node_t *a;
367	extavltree_node_t *b;	353	extavltree_node_t *b;
Line 375...	Line 361...
375	keys_prepare(node_count[ii],2);	361	keys_prepare(node_count[ii],2);
376		362
377	/*	363	/*
378	* AVL INSERT	364	* AVL INSERT
379	*/	365	*/
380	ipl = interrupts_disable();	-
381	s[0][ii] = get_cycle();	366	s[0][ii] = get_cycle();
382		367
383	avltree_create(&avltree);	368	avltree_create(&avltree);
384	for (i = 0; i < node_count[ii]; i++) {	369	for (i = 0; i < node_count[ii]; i++) {
385	avltree_insert(&avltree,alloc_avltree_node());	370	avltree_insert(&avltree,alloc_avltree_node());
386	}	371	}
387		372
388	f[0][ii] = get_cycle();	373	f[0][ii] = get_cycle();
389	interrupts_restore(ipl);	-
390	/*	374	/*
391	* AVL DELETE	375	* AVL DELETE
392	*/	376	*/
393	ipl = interrupts_disable();	-
394	ds[0][ii] = get_cycle();	377	ds[0][ii] = get_cycle();
395		378
396	while (avltree.root != NULL) {	379	while (avltree.root != NULL) {
397	a = avltree_find_min(&avltree);	380	a = avltree_find_min(&avltree);
398	avltree_delete_min(&avltree);	381	avltree_delete_min(&avltree);
399	free_avltree_node(a);	382	free_avltree_node(a);
400	}	383	}
401		384
402	df[0][ii] = get_cycle();	385	df[0][ii] = get_cycle();
403	interrupts_restore(ipl);	-
404		386
405	/*	387	/*
406	* ExtAVL INSERT	388	* ExtAVL INSERT
407	*/	389	*/
408	ipl = interrupts_disable();	-
409	s[1][ii] = get_cycle();	390	s[1][ii] = get_cycle();
410		391
411	extavltree_create(&extavltree);	392	extavltree_create(&extavltree);
412	for (i = 0; i < node_count[ii]; i++) {	393	for (i = 0; i < node_count[ii]; i++) {
413	extavltree_insert(&extavltree,alloc_extavltree_node());	394	extavltree_insert(&extavltree,alloc_extavltree_node());
414	}	395	}
415		396
416	f[1][ii] = get_cycle();	397	f[1][ii] = get_cycle();
417	interrupts_restore(ipl);	-
418	/*	398	/*
419	* ExtAVL DELETE	399	* ExtAVL DELETE
420	*/	400	*/
421	ipl = interrupts_disable();	-
422	ds[1][ii] = get_cycle();	401	ds[1][ii] = get_cycle();
423		402
424	while (extavltree.root != NULL) {	403	while (extavltree.root != NULL) {
425	b = extavltree.head.next;	404	b = extavltree.head.next;
426	extavltree_delete_min(&extavltree);	405	extavltree_delete_min(&extavltree);
427	free_extavltree_node(b);	406	free_extavltree_node(b);
428	}	407	}
429		408
430	df[1][ii] = get_cycle();	409	df[1][ii] = get_cycle();
431	interrupts_restore(ipl);	-
432	/*	410	/*
433	* ExtAVLrel INSERT	411	* ExtAVLrel INSERT
434	*/	412	*/
435	ipl = interrupts_disable();	-
436	s[2][ii] = get_cycle();	413	s[2][ii] = get_cycle();
437		414
438	extavlreltree_create(&extavlreltree);	415	extavlreltree_create(&extavlreltree);
439	for (i = 0; i < node_count[ii]; i++) {	416	for (i = 0; i < node_count[ii]; i++) {
440	extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());	417	extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
441	}	418	}
442		419
443	f[2][ii] = get_cycle();	420	f[2][ii] = get_cycle();
444	interrupts_restore(ipl);	-
445	/*	421	/*
446	* ExtAVLrel DELETE	422	* ExtAVLrel DELETE
447	*/	423	*/
448	ipl = interrupts_disable();	-
449	ds[2][ii] = get_cycle();	424	ds[2][ii] = get_cycle();
450		425
451	while (extavlreltree.root != NULL) {	426	while (extavlreltree.root != NULL) {
452	c = extavlreltree.head.next;	427	c = extavlreltree.head.next;
453	extavlreltree_delete_min(&extavlreltree);	428	extavlreltree_delete_min(&extavlreltree);
454	free_extavlreltree_node(c);	429	free_extavlreltree_node(c);
455	}	430	}
456		431
457	df[2][ii] = get_cycle();	432	df[2][ii] = get_cycle();
458	interrupts_restore(ipl);	-
459	}	433	}
460	printf("\n----------------------------------------------------------------------------");	434	printf("\n----------------------------------------------------------------------------");
461	printf("\nAVL\t\t");	435	printf("\nAVL\t\t");
462	for (ii = 0; ii < TEST_COUNT; ii++)	436	for (ii = 0; ii < TEST_COUNT; ii++)
463	printf("%20llu",f[0][ii]-s[0][ii]);	437	printf("%20llu",f[0][ii]-s[0][ii]);
Line 489...	Line 463...
489		463
490	/** Insert keys of random sequence and delete tree with delete_min functions.	464	/** Insert keys of random sequence and delete tree with delete_min functions.
491	*/	465	*/
492	static void test3(void)	466	static void test3(void)
493	{	467	{
494	ipl_t ipl;	-
495	uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];	468	uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
496	uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];	469	uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
497	unsigned int i,ii;	470	unsigned int i,ii;
498	avltree_node_t *a;	471	avltree_node_t *a;
499	extavltree_node_t *b;	472	extavltree_node_t *b;
Line 507...	Line 480...
507	keys_prepare(node_count[ii],0);	480	keys_prepare(node_count[ii],0);
508		481
509	/*	482	/*
510	* AVL INSERT	483	* AVL INSERT
511	*/	484	*/
512	ipl = interrupts_disable();	-
513	s[0][ii] = get_cycle();	485	s[0][ii] = get_cycle();
514		486
515	avltree_create(&avltree);	487	avltree_create(&avltree);
516	for (i = 0; i < node_count[ii]; i++) {	488	for (i = 0; i < node_count[ii]; i++) {
517	avltree_insert(&avltree,alloc_avltree_node());	489	avltree_insert(&avltree,alloc_avltree_node());
518	}	490	}
519		491
520	f[0][ii] = get_cycle();	492	f[0][ii] = get_cycle();
521	interrupts_restore(ipl);	-
522	/*	493	/*
523	* AVL DELETE	494	* AVL DELETE
524	*/	495	*/
525	ipl = interrupts_disable();	-
526	ds[0][ii] = get_cycle();	496	ds[0][ii] = get_cycle();
527		497
528	while (avltree.root != NULL) {	498	while (avltree.root != NULL) {
529	a = avltree_find_min(&avltree);	499	a = avltree_find_min(&avltree);
530	avltree_delete_min(&avltree);	500	avltree_delete_min(&avltree);
531	free_avltree_node(a);	501	free_avltree_node(a);
532	}	502	}
533		503
534	df[0][ii] = get_cycle();	504	df[0][ii] = get_cycle();
535	interrupts_restore(ipl);	-
536		505
537	/*	506	/*
538	* ExtAVL INSERT	507	* ExtAVL INSERT
539	*/	508	*/
540	ipl = interrupts_disable();	-
541	s[1][ii] = get_cycle();	509	s[1][ii] = get_cycle();
542		510
543	extavltree_create(&extavltree);	511	extavltree_create(&extavltree);
544	for (i = 0; i < node_count[ii]; i++) {	512	for (i = 0; i < node_count[ii]; i++) {
545	extavltree_insert(&extavltree,alloc_extavltree_node());	513	extavltree_insert(&extavltree,alloc_extavltree_node());
546	}	514	}
547		515
548	f[1][ii] = get_cycle();	516	f[1][ii] = get_cycle();
549	interrupts_restore(ipl);	-
550	/*	517	/*
551	* ExtAVL DELETE	518	* ExtAVL DELETE
552	*/	519	*/
553	ipl = interrupts_disable();	-
554	ds[1][ii] = get_cycle();	520	ds[1][ii] = get_cycle();
555		521
556	while (extavltree.root != NULL) {	522	while (extavltree.root != NULL) {
557	b = extavltree.head.next;	523	b = extavltree.head.next;
558	extavltree_delete_min(&extavltree);	524	extavltree_delete_min(&extavltree);
559	free_extavltree_node(b);	525	free_extavltree_node(b);
560	}	526	}
561		527
562	df[1][ii] = get_cycle();	528	df[1][ii] = get_cycle();
563	interrupts_restore(ipl);	-
564	/*	529	/*
565	* ExtAVLrel INSERT	530	* ExtAVLrel INSERT
566	*/	531	*/
567	ipl = interrupts_disable();	-
568	s[2][ii] = get_cycle();	532	s[2][ii] = get_cycle();
569		533
570	extavlreltree_create(&extavlreltree);	534	extavlreltree_create(&extavlreltree);
571	for (i = 0; i < node_count[ii]; i++) {	535	for (i = 0; i < node_count[ii]; i++) {
572	extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());	536	extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
573	}	537	}
574		538
575	f[2][ii] = get_cycle();	539	f[2][ii] = get_cycle();
576	interrupts_restore(ipl);	-
577	/*	540	/*
578	* ExtAVLrel DELETE	541	* ExtAVLrel DELETE
579	*/	542	*/
580	ipl = interrupts_disable();	-
581	ds[2][ii] = get_cycle();	543	ds[2][ii] = get_cycle();
582		544
583	while (extavlreltree.root != NULL) {	545	while (extavlreltree.root != NULL) {
584	c = extavlreltree.head.next;	546	c = extavlreltree.head.next;
585	extavlreltree_delete_min(&extavlreltree);	547	extavlreltree_delete_min(&extavlreltree);
586	free_extavlreltree_node(c);	548	free_extavlreltree_node(c);
587	}	549	}
588		550
589	df[2][ii] = get_cycle();	551	df[2][ii] = get_cycle();
590	interrupts_restore(ipl);	-
591	}	552	}
592	printf("\n----------------------------------------------------------------------------");	553	printf("\n----------------------------------------------------------------------------");
593	printf("\nAVL\t\t");	554	printf("\nAVL\t\t");
594	for (ii = 0; ii < TEST_COUNT; ii++)	555	for (ii = 0; ii < TEST_COUNT; ii++)
595	printf("%20llu",f[0][ii]-s[0][ii]);	556	printf("%20llu",f[0][ii]-s[0][ii]);
Line 621...	Line 582...
621		582
622	/** Simulating timeout mechanismus with insert and delete_min operations.	583	/** Simulating timeout mechanismus with insert and delete_min operations.
623	*/	584	*/
624	static void test4(void)	585	static void test4(void)
625	{	586	{
626	ipl_t ipl;	-
627	uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];	587	uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
628	unsigned int i,ii;	588	unsigned int i,ii;
629	avltree_node_t *a;	589	avltree_node_t *a;
630	extavltree_node_t *b;	590	extavltree_node_t *b;
631	extavlreltree_node_t *c;	591	extavlreltree_node_t *c;
Line 645...	Line 605...
645	/*	605	/*
646	* AVL	606	* AVL
647	*/	607	*/
648	rr = r;	608	rr = r;
649	nc = 0;	609	nc = 0;
650	ipl = interrupts_disable();	-
651	s[0][ii] = get_cycle();	610	s[0][ii] = get_cycle();
652		611
653	avltree_create(&avltree);	612	avltree_create(&avltree);
654	for (i = 0; i < OPERATION_COUNT; i++) {	613	for (i = 0; i < OPERATION_COUNT; i++) {
655	if (((rr % mn) <= nc) && nc) {	614	if (((rr % mn) <= nc) && nc) {
Line 679...	Line 638...
679	avltree_delete_min(&avltree);	638	avltree_delete_min(&avltree);
680	free_avltree_node(a);	639	free_avltree_node(a);
681	}	640	}
682		641
683	f[0][ii] = get_cycle();	642	f[0][ii] = get_cycle();
684	interrupts_restore(ipl);	-
685		643
686	/*	644	/*
687	* ExtAVL	645	* ExtAVL
688	*/	646	*/
689	rr = r;	647	rr = r;
690	nc = 0;	648	nc = 0;
691	ipl = interrupts_disable();	-
692	s[1][ii] = get_cycle();	649	s[1][ii] = get_cycle();
693		650
694	extavltree_create(&extavltree);	651	extavltree_create(&extavltree);
695	for (i = 0; i < OPERATION_COUNT; i++) {	652	for (i = 0; i < OPERATION_COUNT; i++) {
696	if (((rr % mn) <= nc) && nc) {	653	if (((rr % mn) <= nc) && nc) {
Line 720...	Line 677...
720	extavltree_delete_min(&extavltree);	677	extavltree_delete_min(&extavltree);
721	free_extavltree_node(b);	678	free_extavltree_node(b);
722	}	679	}
723		680
724	f[1][ii] = get_cycle();	681	f[1][ii] = get_cycle();
725	interrupts_restore(ipl);	-
726		682
727	/*	683	/*
728	* ExtAVLrel	684	* ExtAVLrel
729	*/	685	*/
730	rr = r;	686	rr = r;
731	nc = 0;	687	nc = 0;
732	ipl = interrupts_disable();	-
733	s[2][ii] = get_cycle();	688	s[2][ii] = get_cycle();
734		689
735	extavlreltree_create(&extavlreltree);	690	extavlreltree_create(&extavlreltree);
736	for (i = 0; i < OPERATION_COUNT; i++) {	691	for (i = 0; i < OPERATION_COUNT; i++) {
737	if (((rr % mn) <= nc) && nc) {	692	if (((rr % mn) <= nc) && nc) {
Line 763...	Line 718...
763	extavlreltree_delete_min(&extavlreltree);	718	extavlreltree_delete_min(&extavlreltree);
764	free_extavlreltree_node(c);	719	free_extavlreltree_node(c);
765	}	720	}
766		721
767	f[2][ii] = get_cycle();	722	f[2][ii] = get_cycle();
768	interrupts_restore(ipl);	-
769	}	723	}
770	printf("\n----------------------------------------------------------------------------");	724	printf("\n----------------------------------------------------------------------------");
771	printf("\nAVL\t\t");	725	printf("\nAVL\t\t");
772	for (ii = 0; ii < TEST_COUNT; ii++)	726	for (ii = 0; ii < TEST_COUNT; ii++)
773	printf("%20llu",f[0][ii]-s[0][ii]);	727	printf("%20llu",f[0][ii]-s[0][ii]);
Line 793...	Line 747...
793		747
794	if (!alloc_nodes(NODE_COUNT))	748	if (!alloc_nodes(NODE_COUNT))
795	return NULL;	749	return NULL;
796		750
797	/*	751	/*
798	* Disable interrupts,	-
799	* store initial cycle count,	752	* store initial cycle count,
800	* do test,	753	* do test,
801	* store finish cycle count,	754	* store finish cycle count,
802	* enable interrupts,	-
803	* show results	755	* show results
804	*/	756	*/
805		757
806	test1();	758	test1();
807	test2();	759	test2();

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/timeout/timeoutbench1.c – Rev 2431 → 2450