Hacker News new | past | comments | ask | show | jobs | submit login

Both replies as I write this are ignoring the question I was answering. The question was, how can a compiler implement a linked list as anything other than a linked list? The answer is what I gave. Being a compiler, it may also do things like an analysis of the use cases to prove that there are no relevant changes to performance (or that performance only improves) and fall back to a "true" linked list if it can't prove how it is being used, or, being a compiler, it may just tell you to get stuffed and deal with the performance differences. Depends on the choices the compiler author(s) made.

But just because Lisp has cons and cdr does not mean the compiler is obligated to only and exactly use things that structurally look like linked lists in the actual implementation. You need to break the relationship between memory layout and API to understand what is going on here. You may choose later to put them back together; the naive memory layout is often a good one. (Linked lists nowadays are arguably one of the larger exceptions to that, but there are still circumstances even so where that may not be an issue; see Erlang's memory management for instance and ponder how that impacts linked list locality.) But you can't understand what compilers may be doing if you do not realize that there is a distinction.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: