Extension performance comparison among lists

by Tao Feng (modified: 2008 May 21)

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.<br> I extend [INTEGER, INTEGER] into the lists, and calculate time and memory usage (increase).<br> 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

Comments
  • Colin Adams (9 years ago 21/5/2008)

    Initial sizes for arrayed lists

    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

  • Jocelyn Fiat (9 years ago 22/5/2008)

    LINKED_LIST.extend and put_front ...

    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.

  • Tao Feng (9 years ago 22/5/2008)

    Initial size.

    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.<br> 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.<br> 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.

    • Colin Adams (9 years ago 22/5/2008)

      Avoid reallocation

      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

    • Eric Bezault (9 years ago 22/5/2008)

      Time spent in GC?

      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.

      • Tao Feng (9 years ago 22/5/2008)

        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.<br> 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.