git.iko.soy/streamly
on master help sign in
streamly/docs/Developer/linked-lists.md
32 lines 1.9 kB history raw
1# Linked Lists
3The immutable Haskell lists or streams are great for stream processing.
4However, they may not be suitable for purposes where we need to store data for
5a longer while. In such cases we need mutable linked lists in pinned memory for
6high performance applications i.e. we need the C like linked lists. Here are
7some cases where linked-lists may be warranted instead of immutable lists:
9* Let's say we want to buffer incoming data in a list. The buffered data may be
10 millions of elements. When we are buffering we may allocate cells from
11 different areas of the GC heap. When there are other activities going on we
12 may have to keep copying this buffered data during GCs. When we consume this
13 buffer, again it creates a fragmented heap and we may have to copy some other
14 long-lived data to defragment the heap. The point is that we should not have
15 long-lived data in the GC heap.
17* When we delete a node in the list, Haskell lists have to be recreated
18 generating a lot of garbage. We cannot take a reference to the unmodified
19 segments and reuse them in the new list. On the other hand with mutable
20 linked-lists we can delete a node cheaply. This could be a common case in a
21 hash table collision chain which requires deletion of elements.
23* Similar to deletion, if we need to insert an element in the middle of the
24 list, an immutable list has to be re-created.
26* To implement a queue, two lists in the immutable model can be used
27 efficiently if we are strictly adding at the end and deleting from the front
28 and if there is sufficient batching so that swapping of the lists is not a
29 common operation. If we have to insert elements in the middle or if we have
30 to swap too many times again we will have the same GC issues as stated above.
31 For example, in implementations of priority search queues or timer wheels we
32 have to mutate the lists.