eiffelroom - Extension performance comparison among lists - Comments

That's a good point. I don't

ted_eiffel — Thu, 22 May 2008 08:59:02 -0700

That's a good point. I don't disconnect items in the lists. So GC basically only collects objects that were temporarily used in the list operations, rather than those tuples. This part of GC should be taken into account when measuring their performance of those lists. However, if I do tests creating no new tuples, we know performance of lists in real applications should be in between.
I thought about another GC problem. I am not sure how GC exactly acts between "full_collect"s. I thought the later list testing could be affected by previous ones, as some stack chunks in the runtime may already allocated by previous testing in the same application.

Time spent in GC?

ericb — Thu, 22 May 2008 02:35:26 -0700

One problem with linked lists is that it creates many objects, so it will trigger more GC cycles. So the benchmarks may look totally different if the code is part of a real application which already has a lot of objects in memory.

Speaking about the GC, if you just want to measure the data structure impact, it might be worth trying to always insert the same tuple object instead of creating a new one at each iteration.

Avoid reallocation

colin-adams — Wed, 21 May 2008 23:47:16 -0700

You should avoid reallocation by allocating a large memory block initially. Try allocating one twice the size you need - despite the unused memory allocated, it should still be faster than the linked version. Colin Adams

Initial size.

ted_eiffel — Wed, 21 May 2008 17:55:17 -0700

I didn't preallocate a size for arrayed lists. Firstly, I wanted to test the situation I completely don't know how many elements there would be. In practice, however, we can approximately evaluate the number of elements to be used. Secondly, yes, no doubt, the arrayed list is much faster and uses less memory, when known size is preallocated. That is an easy situation, if elements of the list are not frequently inserted/removed/moved, I choose that way without problem.
Now even I don't preallocate size for arrayed lists, they seem faster when I know the number of elements is not too huge. That's to say, no matter if I preallocate the size, it is better to use arrayed lists as long as not many elements and no element moving around.
When the number is very large, the big memory block reallocation is very slow for arrayed lists, so linked lists become faster since they only allocate small blocks of memory.

LINKED_LIST.extend and put_front ...

Jocelyn Fiat — Wed, 21 May 2008 12:22:52 -0700

LINKED_LIST.extend can have similar performance than LINKED_LIST.put_front if you take care of moving the cursor

lst.extend (entry) lst.finish

Otherwise, for each extend, it will search again for the last element. As far as arrayed list (or any fixed size), this is always much faster to initialize with the expected size, otherwise each time it resizes the underlying array, it will increase the size for its needs ... and then each time it is new allocation of memory.

Initial sizes for arrayed lists

colin-adams — Wed, 21 May 2008 08:44:22 -0700

These tests make linked lists look faster than arrayed lists. For arrayed lists, you should allocate the expected size - in this case the number of elements you are going to add.

Then you should see a big difference.

Colin Adams

Extension performance comparison among lists

ted_eiffel — Wed, 21 May 2008 03:14:12 -0700

I did a small app to benchmark extension performance of major Eiffel list data structures on my Win32 XP machine, using EiffelStudio 6.2.7.3489, Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42 for 80x86, Microsoft (R) Incremental Linker Version 8.00.50727.42.
I extend [INTEGER, INTEGER] into the lists, and calculate time and memory usage (increase).
Note: I use `put_front' instead of `extend' in LINKED_LIST, because of the way `extend' of LINKED_LIST is too slow to compare with others.

Lists Benchmarked

DS_LINKED_LIST (Gobo 3.8)

DS_ARRAYED_LIST (Gobo 3.8)

LINKED_LIST (ELKS Revision: 166)

ARRAYED_LIST (ELKS Revision: 164)

Conclusion

The situation is restricted in small reference objects like tuples. The conclusion is based on this and on the context of the compiler/OS/hardware.

Arrayed lists are faster than linked lists when numbers of extension elements is not too huge.
Arrayed lists always beat linked lists at memory usage.
When the number of extension elements is not too huge, less then 200,000, ARRAYED_LIST shows its best performance and memory usage. (DS_ARRAYED_LIST is good as well)
When the number of extension elements raises to more than 200,000, DS_LINKED_LIST starts to show its best performance.
LINKED_LIST is always slower then DS_LINKED_LIST. But less memory usage at all time.

Also see Detailed Benchmark Result.

Detailed Benchmark Result

All data bellow was from finalized binary.

-Performance-

TIMES	DS_LINKED_LIST	DS_ARRAYED_LIST	LINKED_LIST	ARRAYED_LIST
10000	0.000	0.000	0.000	0.000
30000	0.016	0.015	0.016	0.016
50000	0.047	0.016	0.047	0.015
100000	0.110	0.063	0.172	0.080
200000	0.218	0.234	0.235	0.202
300000	0.343	0.438	0.359	0.406
400000	0.485	0.563	0.547	0.531
500000	0.610	0.781	0.672	0.782
600000	0.703	1.016	0.781	1.000
700000	0.844	1.328	0.953	1.344
800000	1.000	1.453	1.063	1.515
900000	1.094	1.719	1.219	1.969
1000000	1.218	2.156	1.313	2.250
1600000	1.954	4.218	2.140	4.421
3200000	3.907	13.375	4.422	13.719

Time uses in seconds.

-Memory Usage-

TIMES	DS_LINKED_LIST	DS_ARRAYED_LIST	LINKED_LIST	ARRAYED_LIST
10000	0	0	0	0
30000	0	0	0	0
40000	0	0	0	0
50000	4194352	0	0	0
60000	4194352	0	0	0
70000	4194352	0	0	0
80000	4194352	0	0	0
90000	8388704	0	0	0
100000	8388704	0	0	0
110000	8388704	0	4194352	0
120000	8388704	4194352	4194352	4194352
140000	12583056	4194352	8388704	4194352
160000	12583056	4194352	8388704	4194352
180000	20971760	4194352	16777408	8388704
200000	20971760	4194352	16777408	8388704
250000	20971760	8388704	16777408	12583056
300000	25166112	12583056	16777408	16777408
400000	37749168	16777408	25166112	25166112
500000	46137872	25166112	33554816	25166112
600000	54526576	37749168	41943520	37749168
700000	67109632	41943520	62915280	46137872
800000	75498336	46137872	71303984	50332224
900000	83887040	59921060	79692688	59921060
1000000	92275744	64115412	83887040	64115412
1600000	150996672	109954228	138413616	114148580
3200000	306187696	236755304	293604640	240949656

Memory uses in bytes.

Code to perform the test

class

    APPLICATION

inherit

    MEMORY

create

    make

feature -- Initialization

    make (args: ARRAY [STRING]) is

            -- Run application.

        local

            l_gobo_linked_list: DS_LINKED_LIST [TUPLE [a, b: INTEGER]]

            l_gobo_arrayed_list: DS_ARRAYED_LIST [TUPLE [a, b: INTEGER]]

            l_elks_linked_list: LINKED_LIST [TUPLE [a, b: INTEGER]]

            l_elks_arrayed_list: ARRAYED_LIST [TUPLE [a, b: INTEGER]]

            test_linked_list: BOOLEAN

            l_start_time, l_finish_time: TIME

            i: INTEGER

            mem_start: INTEGER

            mem_info: MEM_INFO

        do

            total := args.item (1).to_integer

            test_linked_list := args.valid_index (2) and then args.item (2).is_case_insensitive_equal ("y")

            print ("The following is the time comparison among lists of insertion%N")

            print ("----------------------------------------------------%N")

            mem_info := memory_statistics (total_memory)

            ---------------------------

            create l_start_time.make_now

            full_collect

            mem_info.update (total_memory)

            mem_start := mem_info.total

            from

                i := 1

                create l_gobo_linked_list.make_default

            until

                i > total

            loop

                l_gobo_linked_list.force_last ([0, 0])

                i := i + 1

            end

            create l_finish_time.make_now

            print ("Gobo linked list (DS_LINKED_LIST): ")

            print ((l_finish_time - l_start_time).duration.out)

            l_start_time := Void

            l_finish_time := Void

            full_collect

            mem_info.update (total_memory)

            print ("Memory increase: " + (mem_info.total - mem_start).out + "%N")

            l_gobo_linked_list := Void

            ---------------------------

            create l_start_time.make_now

            full_collect

            mem_info.update (total_memory)

            mem_start := mem_info.total

            from

                i := 1

                create l_gobo_arrayed_list.make_default

            until

                i > total

            loop

                l_gobo_arrayed_list.force_last ([0, 0])

                i := i + 1

            end

            create l_finish_time.make_now

            print ("Gobo arrayed list (DS_ARRAYED_LIST): ")

            print ((l_finish_time - l_start_time).duration.out)

            l_start_time := Void

            l_finish_time := Void

            full_collect

            mem_info.update (total_memory)

            print ("Memory increase: " + (mem_info.total - mem_start).out + "%N")

            l_gobo_arrayed_list := Void

            ---------------------------

            if test_linked_list then

                create l_start_time.make_now

                full_collect

                mem_info.update (total_memory)

                mem_start := mem_info.total

                from

                    i := 1

                    create l_elks_linked_list.make

                until

                    i > total

                loop

                    l_elks_linked_list.put_front ([0, 0])

                    i := i + 1

                end

                create l_finish_time.make_now

                print ("ELKS linked list (LINKED_LIST): ")

                print ((l_finish_time - l_start_time).duration.out)

                l_start_time := Void

                l_finish_time := Void

                full_collect

                mem_info.update (total_memory)

                print ("Memory increase: " + (mem_info.total - mem_start).out + "%N")

                l_elks_linked_list := Void

            end

            ---------------------------

            create l_start_time.make_now

            full_collect

            mem_info.update (total_memory)

            mem_start := mem_info.total

            from

                i := 1

                create l_elks_arrayed_list.make (1)

            until

                i > total

            loop

                l_elks_arrayed_list.extend ([0, 0])

                i := i + 1

            end

            create l_finish_time.make_now

            print ("ELKS arrayed list (ARRAYED_LIST): ")

            print ((l_finish_time - l_start_time).duration.out)

            l_start_time := Void

            l_finish_time := Void

            full_collect

            mem_info.update (total_memory)

            print ("Memory increase: " + (mem_info.total - mem_start).out + "%N")

            l_elks_arrayed_list := Void

        end

    total: INTEGER

end -- class APPLICATION