• 0 Posts
  • 5 Comments
Joined 1 year ago
cake
Cake day: October 9th, 2023

help-circle
  • Not just trees; any operation that involves mutating or manipulating list-like structures is more efficient than arrays.

    Some examples:

    Removing an element is delinking a single cons cell, vs either copying to a new array or shuffling all subsequent elements left. It also doesn’t break any references to list cells, even the removed cell.

    Slicing, at minimum, only requires having the cons cell at the new head of the list; rather than either a special datastructure to represent a slice, or copying to a new array.

    Filtering means pulling cons cells from a nursery on an ad-hoc basis, using them to collect filtered elements into a new list of unknown length. With an array, you need a pre-allocated buffer that either sets a limit on the size of the filtered set, or requires reallocation on resize with a O(n) copy.

    Just, in general, you can be a lot more relaxed with flinging data around lists without having to think about the algorithmic overhead of allocating, reallocating, copying and shuffling arrays.


  • If you were to use Janet arrays as one uses lists in a lisp, then you’d quickly find yourself in a performance tar pit. Arrays would be frequently allocated, freed, resized, copied, and so forth.

    A linked list built around cons cells allows slicing, augmentation, filtering, and so on almost for free.

    That means writing in a proper lisp lends itself towards almost thoughtlessly mutating and manipulating lists; whereas writing code in Janet means spending more care about what you’re doing with the data structure.