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