Published on: 2020-05-21T15:36:02+00:00
Cheney's semispace collector, although effective, requires twice as much memory during collection. However, a proposed solution suggests storing tospace objects in a disk file instead of core memory, making it more suitable for devices with larger free disk space than memory space. Comparatively, the in-place array-sorting form of qsort, known for its speed, reduces cache pressure by touching smaller amounts of memory. This is possible because elements in an array are of equal size, allowing for constant space swapping.To improve efficiency, Cheney's semispace collector can be transformed into an in-space algorithm by making all objects a constant fixed size using linked lists. By swapping nodes around, similar swap operations can be used. Additionally, routing queries, which are read-only, do not violate the tri-color invariant and can be paused after advancing the scan pointer. This allows the thread to service routing queries, gossip updates, or channel closes. Channel objects can be managed using a freelist, while the garbage collector is only used for the nodes themselves. Furthermore, once the Cheney algorithm ends, nodes beyond the scan/alloc pointer are considered unreachable from that node, allowing for immediate failure of routefinding queries for nodes beyond this border.The Lightning Network aims to facilitate fast and affordable transactions on the Bitcoin blockchain. To account for potential size increases and enable running Lightning Network nodes on less-capable devices, reducing the size of the routemap representation is crucial. A proposed solution involves using an array-based storage system where nodes and channels are stored in two large arrays, with references to channels and nodes being indices into the array rather than pointers. This reduces the overhead of managing objects of varying sizes.Deletion of channels and nodes from the routemap can be accomplished using a freelist, but the use of Cheney 2-finger Garbage Collection is suggested. Cheney 2-finger Garbage Collection is a copying semispace collector that copies live objects into a new memory space and recovers and reuses garbage and copied-from memory. The order of object scanning follows a breadth-first approach, which provides a heuristic for pathfinding.The article explores how Cheney's algorithm can be used in pathfinding algorithms, guiding the opening of nodes and evaluating paths based on fees and other factors. It also addresses the issue of semispace collection requiring double the memory during collection. To mitigate this, the suggestion is to write tospace objects into a disk file and reload the in-memory arrays from the tospace file(s) once the Cheney run is complete.Incremental collection and the tri-color abstraction are discussed as ways to handle changes to the routemap. Incremental collection allows incoming changes to the routemap graph to be accepted while maintaining responsiveness during a collection. The tri-color abstraction helps determine if a fromspace object is black, gray, or white without additional memory representation.Finally, the article mentions tenuring as a solution against losing subgraphs. By selecting nodes with long-lived channels and adding them to the root set, Cheney can be executed accordingly. After Cheney completes its run, any tenured nodes still marked as white (without forwarding pointers) can be added to the gray set by copying them to tospace and advancing the allocation pointer.
Updated on: 2023-07-31T22:57:09.159767+00:00