Eina Arrays are compact memory-structures but are bad at modifications that append, insert or remove. Over-allocating the end can alleviate some of the appending issues but none of the others.
Eina Lists are double-linked lists and are great for append, prepend, insert and remove, but are very costly in terms of memory footprint and costly to walk due to cache inefficiency.
This is intended to be able to replace many uses of Eina Lists (not Inlist) inside EFL and other places to have faster list operations and smaller memory footprints. It requires work to go replace it and in some cases it's hard as external APIs rely on there being an Eina List returned or ingested by the API.
This includes test code that does a set of operations to an Eina List and a BList (from walking to modifications of various types). My benchmarking shows that BList is somewhere about 5x-10x faster in this test (depending on number of iterations and list length) vs. Eina List and uses about 20% of the memory vs. Eina List. Those are fairly impressive numbers for a first-stab at this, so it's worth looking more into this.
This is a proposal for something that strikes a balance between the 2. It's a "Block List". A double-linked list of "blocks" of arrays. Insert, Remove, Append, Prepend are relatively cheap, and walking is now more efficient too. Far more. A block size has been chosen at 128 bytes for this as this is a single cache line on some architectures and 2 sequential cache lines on almost all others. That block contains pointers to the next/previous blocks (also squeezing in the element count into the lower 7 bits due to this 128 byte alignment). The rest of the block is data pointers in an array.
When an item is removed or inserted all items in the array are shuffled up/down that are after that item. If the array is full then a new block may be created after this one. If the block goes to a 0 population count, it is freed and the neighboring blocks in the list are re-linked. Precisely when frees do happen or not is an implementation detail though.
The API looks different to arrays and lists as it tries to have the properties of both the list and array APIs in Eina. The BList is auto-allocated when first having any content added, and de-allocated when the last item is removed, thus a NULL BList handle is an empty BList. you don't have to worry about allocating/deallocating the BList separately to inserting or removing items.
It only accepts pointers as content because accepting entire data structures probably is not worth it. I have not implemented any Eina Iterator or Accessor as it's not an absolute requirement at this point to discuss API and general design. It doesn't have full documentation yet because this is more about discussing design and ideas and direction.
I have been careful to design the API to hide the implementation (unlike Eina Lists) specifically so that the implementation can change. either over time it can be optimized or even at runtime BList could transform how ti stores things based on usage patterns. it could flatten out a BList that is almost never modified into a big array, or choose different block sizes. I think it's important to make this opaque and hide such details for future speedups.
This has only one downside vs. Eina List - you cannot keep an "Eina_List *" style pointer handle to the list node around. With Eina List such handles can be stored inside other structures for instant O(1) access to the list node to then be able to de-link the object without hunting for it etc. Indexes can't work either as the index can change with modifications to the BList (items before and indexed item can be removed or inserted). The API does support a form of handle (Eina_Blist_Item *) but this is intended as a temporary handle only and can only be valid until the BList is modified. Once modified this handle is then invalid. This leads to eina_blist_clean() and eina_blist_clean_force() as explicit "clan up this list please" calls (this first may do nothing if it doesn't think it's worth cleaning up, and the second forces a cleanup/defrag etc. even if it's probably not worth it), so modifications to the list have to be explicit and reading can't modify it because you need to know when an item handle may invalidate.
In addition the list supports a free function (like Eina Hash does) that is called when the BList is freed on all items still in the BList or when items are removed from it as a convenience to cut down remembering to do it yourself.
This patch review is a bit of an RFC about this. Adding it to Eina is just adding extra code (until it's in use), but it can't be stable/public API until it's "acceptable" and so the API design and anything it implies or that affects it are really key here.
This is just some code to review and examine. I've uploaded the raw files here
To compile and run:
gcc blist.c eina_blist.c -o blist `pkg-config --cflags --libs eina` time ./blist blist 10000 1000 time ./blist list 10000 1000
You will probably find the list test is about 10x slower than the blist one. e.g:
./blist blist 10 1000000 1.76s user 0.00s system 99% cpu 1.761 total ./blist list 10 1000000 7.85s user 0.00s system 99% cpu 7.854 total (4.5x) ./blist blist 100 100000 1.70s user 0.00s system 99% cpu 1.707 total ./blist list 100 100000 7.95s user 0.00s system 99% cpu 7.957 total (4.7x) ./blist blist 1000 10000 1.76s user 0.00s system 99% cpu 1.765 total ./blist list 1000 10000 9.95s user 0.00s system 99% cpu 9.959 total (5.7x) ./blist blist 10000 1000 3.96s user 0.26s system 99% cpu 4.225 total ./blist list 10000 1000 49.58s user 0.00s system 99% cpu 49.587 total (11.7x) ./blist blist 100000 10 3.70s user 0.03s system 99% cpu 3.728 total ./blist list 100000 10 43.89s user 0.00s system 99% cpu 43.890 total (11.7x) ./blist blist 1000000 1 43.20s user 0.02s system 99% cpu 43.227 total ./blist list 1000000 1 460.35s user 0.04s system 99% cpu 7:40.430 total (10.7x)
Note that speed up get bigger the longer the list, but are about the range of 5-10x. Heap usage is also improved bout about 5x as well.
If your system is very slow, remove a 0 digit from the 2nd parameter (how many times it does the same test - loops).
So thoughts, improvements? Design changes? Reasoning behind them? This isn't worth it?