Would intrusive collections modeled after the boost intrusive boost intrusive 1.75.0 collection be a useful addition for Julia. Does Julia already have mechanisms which make such collections superfluous.
Consider the advantages of intrusive collections from the linked page:
Intrusive containers can be used for highly optimized algorithms, where speed is a crucial issue and:
additional memory management should be avoided.
the programmer needs to efficiently track the construction and destruction of objects.
exception safety, especially the no-throw guarantee, is needed.
the computation of an iterator to an element from a pointer or reference to that element should be a constant time operation.
it’s important to achieve a well-known worst-time system response.
localization of data (e.g. for cache hit optimization) leads to measurable effects.
I will post some experimental code (i am still learning the language) in the coming day, but wanted the community feedback to see if this is worth spending time on.
From a first glance it seems that this library/concept aims to solve a specific C++ problem: STL performance issues.
If Julia suffers from similar problems I don’t know, AFAIK not too much in this direction was reported here.
What Julia doesn’t have (again AFAIK) in its standard library is something like “well-known worst-time system response” which was mentioned for boost.
I am not entirely sure if this is possible in Julia, you can try writing code that does not allocate, and even disable the garbage collector, however, in many cases it is not possible (or desirable) to avoid all allocations or make them all before some barrier (i.e., preallocating everything, disabling GC, and then doing all the computation).
This is not just to prevent GC. Actually the main advantage is removal of object from a collection with O(1) complexity.
You could have an object that is indexed into a hashmap and also stored in a linked list. With the non intrusive linked list, you cannot remove an object in O(1), the complexity is O(n).
Actually the main advantage is removal of object from a collection with O(1) complexity. If an object is present in a hashmap and a linked list, once you lookup the object in the hashmap, removal from the linked list has O(1) complexity.
Do you have a definition of intrusive collections? The link you gave do not try to define what make a collection or list intrusive it only gives the advantages and some ways to use them, but it does not say what exactly they are (what makes them different from non-intrusive counterparts structurally), i.e., how they are implemented.
There’s an implementation of an InvasiveLinkedList in Base, though typically in Julia intrusive collections are not required (indeed, even for C++ the bottom of the boost page says they are more difficult to use and should be avoided). You can typically solve the problem of removing an object from the linked list by only using hash maps, which also already have O(1) complexity and generally also all of the other properties you highlighted.
What if my object needs to be in a hashmap and a linked list? Removal from hashmap is definitely O(1) but linked list removal is O(n) if the object is not at the ends of the linked list.
Actually, InvasiveLinkedList is an excellent start, almost there except that the removal of an item is not O(1). I am going to use that as a starting point and model an instrusive list around that. Thanks for pointing it out.
Here is a first stab at an intrusive list in julia (i am still in the early learning stages of julia, so this code snippet is just to illustrate the idea) - Julia Intrusive List
So the type T that can be managed by this list needs to provide the fields prev and next. As you can see the removal of an item is O(1).
A typical scenario in my usage (in C++ using the boost::intrusive collections) is to store an item in an intrusive hash map - for quick lookup by id. And this item is also held in a linked list to preserve arrival order. A lot of times the item needs to be removed from both collections, after the item has been looked up and removed from the hash map, typically an O(1) operation, it can be removed from the linked list with O(1) complexity as well.