Chapel: [Design] Interface of UnrolledLinkedList

[Rapiz1]

Unrolled Linked List

No sight of it in other langauges or popular libraries.

The use case would be on a machine whose memory is small and cahce miss is expensive. Users can trade off between time and space by specifying the number of elements in one node.

vs Linked List

|Unrolled|Normal|
|-|-|
|Less memory overhead| |
|Slower insertion and deletion in the same node| |
|Better cache performance| |

Interface

Same as List except an addtional init argument
Also add parallel iterator

[cassella]

Should UrolledLinkedList have a parSafe param?

I might also give it a this(), and erase(pos) as in Vector.

The LinkedList concat(l) adds a copy of each element of l to this. There's another version of concat() that would be good for ULL (and for LinkedList): move the actual element of l to this, leaving l empty. The reason this is attractive for linked lists is that it can be done in constant time: just change a constant number of next pointers (and prev pointers if it's doubly-linked) and it's done.

(The usual use case would be if l were a temporary list that exists for the purpose of having its elements moved to this. You could imagine multiple tasks creating their own temporary lists in parallel, then having to take a global lock on this only once.)

Maybe also a split(pos) to create two lists from one, though it's not quite as cheap if the split point is in the middle of a node.

[cassella]

I'm also thinking destroy() (as a public method) should probably be called clear() instead, here and in LinkedList. And also add one to SkipList and IntervalTree.

[Rapiz1]

@cassella Yes, it should have parSafe, this, these. I omitted these general procedures/variables.
I think slicing and linking nodes could be very useful for (unrolled) linked list. I agree with adding that. split(pos) also sounds good. But I think we can pass a reference of the node to the procedure to reduce the complexity to locate the node. And these should also be done for the linked list, not only for the unrolled version.

[cassella]

How would the caller get a reference to a node? I would expect that object to be private to ULL, and no part of the interface as proposed returns one -- everything is in terms of eltTypes.

[Rapiz1]

Operations about nodes are still my primitive thoughts so not proposed here. What's proposed here is just the basic part(same as the original linked list).
If we want to take full advantage of the linked list slicing and linking, then we have to expose nodes to users. Or it's just a list that can be pushed into and poped.

We could make these yield ref to nodes.
Also,

• front(): ref Node
• back(): ref Node

[cassella]

init(eltType, maxElements=defualtMaxElement, parSafe)

Should be "default", not "defualt". :)

[Rapiz1]

After some thoughts, I'd like to keep things simple and the interface the same as the original LinkedList.

Without doubts, split and concat( without copying ), slicing/linking nodes are great. But I don't think it's a good idea to provide split(pos) in O(N). Because even copying and delete nodes with brute force, it's O(N). Yes, split is still slightly faster but that's not a notable improvement. And it's confusing to the newcomers who will suppose that splitting a list costs O(1). We have to provide users with access to nodes in some way to really make operations fast.

So here comes the question, should users have direct access to the structure implementation we provide?
In many libraries that target at providing containers, the answer is no.
However, there is Boost. Intrusive. Providing access to the linked nodes is kind of like the idea ofBoost.Intrusive, exposing the implementation to users thus giving them very powerful operations. However, if I do target on making a module like Boost.Intrusive and I want to keep things unified for this DS project, it means too much work and design discussion for a summer. I consider this project as a container library and I'm not expecting much. So I'd like to keep the interface as LinkedList.

[cassella]

It might be interesting to have a parallel iterator for the unrolled linked list. It seems pretty natural to let each task process some number of nodes; or even to divide up the elements within a node (depending on the node size).

[Rapiz1]

It might be interesting to have a parallel iterator for the unrolled linked list. It seems pretty natural to let each task process some number of nodes; or even to divide up the elements within a node (depending on the node size).

I agree with you. Added that.

[Rapiz1]

Oh I forgot to update this issue.

Some discussion in https://github.com/chapel-lang/chapel/issues/15669

@e-kayrakli

UnrolledLinkedList: The argument of potentially faster insertion is not enough for me to making this a separate structure. I think we should try hard to make this an implementation of List. And naturally, if we do that it'll also follow the path of Vector.

@bradcray

I had imagined LinkedList also being an implementation option under list which is why I was suggesting putting UnrolledLinkedList there as well.

And I'm actually working on it as it's an implementation option under list.