mercredi 10 janvier 2024

Linked list vs GC in CLR

Due to my not exactly very deep understanding of how GC works (it's 40k lines of C source in CLR's runtime, I just can't can) and the necessity of using both doubly-linked and very big data storage, let's consider if it is exactly a viable solution to use a System.Collections.Generic.LinkedList<T> as a storage for that.

For a better understanding, there are some hints about the data to be stored (you can aswell skip):

  1. The entire collection should be locked in memory all the time. It means no swapping, being paged out of memory or being 'manually' written to a file, because the access to first and last elements should be very fast.
  2. The data is continuously both added to the "head" and removed from the "tail". The data rate can be pretty high, meaning a lot of new objects are created and added to the front and a lot of data is detached from the back of the list, making them eligible for GC.
  3. The ammount of data items added is always equal to ammount of items removed.
  4. The ammount of data to be stored is actually pretty high too. The roughly estimated memory requirement is being from 20 to 200 Mb. The ammount of required memory is fixed and known at a 'collection' instantiation time.
  5. Every data item is a strongly-typed recursively-unmanaged struct. It means that it can be easily serialized to a byte array forth and back.
  6. It should always be trivial to access at max two neighbour elements.
  7. The performance impact of using such a big data storage should be minimal.

The main concern that bothers me is as follows: won't it rely too hard on a GC, making GC use a lot of CPU time (GC pressure) just to traverse an object graph? Or, maybe a sweep phase will become a nightmare? My poor understanding and basic intuition tell me that (huge quantity of objects) + (every one of them holding a reference to the next one) + (a lot of newly-created 2nd-generation objects that are detached from tail) = (a lot of GC time).

Should I rather consider using an unmanaged heap as a solution? Because of the size being fixed, the approximated procedure as I see it should be as follows:

  1. At an application initialization, request a huge page from an OS. The best would be to have a single 256 Mb page (not sure if it is possible to have 256 Mb page on x86_64 or an ARM). Fall back to a regular malloc (Sytem.Runtime.InteropServices.NativeMemory.Alloc(nuint) method in CLR) or VirtualAlloc for Windows via kernel call, or some Linux equivalent.
  2. Allocate some kind of a free list in this region.
  3. Keep track of the ammount of data added. As soon as the region is full, simply overwrite 'tail' elements.
  4. Drop (free) the region if it will be no longer needed for an app operation.

Personally I would prefer the later, because it does not require deallocations of every single detached object, no sweeping is required either. Using huge pages where possible will make pointer dereferencing faster (I believe in CLR it is also the case). The other benefit is an implementation detail, but useful to know in case you didn't - huge pages are locked by an operating system in memory, so they will never be swapped out. On the other hand, it will require a little bit of self-made PAL (Platform Abstraction Layer) and clearly writing some 'unsafe' code - either by using pointers and C#'s unsafe or System.CompilerServices.Unsafe static methods along with managed refs and ins. The other way would be perhaps using some kind of a ring-shaped array, but let's save that for another question on SO.

I know that the best solution is to make both approaches undergo a benchmark, but according to your experience, how would you implement this?

Aucun commentaire:

Enregistrer un commentaire