Luke Gorrie (lukego) wrote,
Luke Gorrie

Heap: the invisible data structure

Imagine for a moment that all the lists in our programs suddenly switched to the performance characteristics of vectors, and vice-versa. Wouldn't that be awkward? Imagine even worse: that in SBCL they behaved as normal, in Lispworks they were switched, in Allegro they both behaved like balanced trees, and in OpenMCL it was all undefined. How would we write programs then, without depending on things we take for granted like fast vector random-access and APPEND only taking time proportional to the left-hand list's length?

It would be bloody hard. We'd have to avoid sequences as much as possible not only in code that has to be fast but also in code that just has to be predictable. Our programs would surely be awkward to read because of all the squirming to avoid calling sequence functions.

Thank goodness this is just a dream. It would be too silly.

Now imagine for a moment that an even more fundamental data structure lacked good and predictable behaviour that you could depend on: the pervasive garbage-collected heap. What then, I ask you?

Update: Feedback suggests that this post didn't make the point I wanted to. I hope my sbcl-devel post helps to say what I'd like to have as a Lisp user.
Tags: garbage collection, hacking, lisp
  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.