eiffelroom - memory usage - 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