5 ms·

I really liked the Art of Computer Programming with regards to this subject. While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for d

I really liked the Art of Computer Programming with regards to this subject. While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for dynamically changing arrays or other data structures. The book also builds up to garbage collection and how to implements Lisp-lists. The kind of encyclopedic knowledge you'd expect from Knuth. ------- One of my favorites is how to have two Arrays dynamically take up one space. Have one array grow normally from location#0, and the second array grow backwards from location#End. Now both arrays take up the statically allocated space efficiently sharing. This can be extended to an arbitrary number of arrays, but at that point you might as well use Malloc and Realloc. Or at least, the techniques therein are really close to a malloc-like routine IMO.

Retr0id 3y ago
SQLite's on-disk format uses a similar array technique for storing the contents of table btree leaf node pages. Within a fixed-size page, there's an array of offsets growing forwards, and an array of (variable length) row values growing backwards from the end - the latter of which may end up with holes when rows are deleted (iiuc). It wouldn't surprise me if it was a direct inspiration, since their docs cite TAOCP for the btree structure itself.
- hiAndrewQuinn 3y ago
  We know from the Corecursive podcast on the hidden story of SQLite that Dr. Hipp did indeed reference and pull at least one alg straight from Knuth's books, which he had behind his desk. What a different world that must have been!
  - andrewshadura 3y ago
    FYI, he's D. R. Hipp, not Dr. Hipp.
    - jcgrillo 3y ago
      More like Dr. D. R. Hipp, actually.
      - tomcam 3y ago
        Hilarious and true
      - jeffrallen 3y ago
        Great rapper name.
    - deleted 3y ago
      [deleted]
- felixge 3y ago
  This sounds like it was copied from PostreSQL which SQLite cites as a strong source of inspiration.
- tanelpoder 3y ago
  Oracle does this as well and I suspect many other row-major RDBMS storage engines do too.
- suncherta 3y ago
  As others have already mentioned this is used in a lot (most?) of databases. It is called "slotted-page". Searching for it gives good discussions/explanations of it.
shadowgovt 3y ago
This succinctly describes how old MacOS allocated per-application resources. Each app had a minimum and preferred RAM requirement tagged to it. When launched, it would take up the whole preferred slot, unless that amount wasn't available in which case it'd take up less than preferred (and fail to launch if it couldn't get minimum). The system allocated the heap (and libraries, I think) at the bottom and the stack at the top of that physical-RAM slice, and off you went. I believe around system 8 they added a virtualization layer that started to obviate the need for that approach (and of course by the time of MacOSX they were using paged memory like everyone else was and so such fancy tap-dancing was no longer needed). But it's fun to think about the era where this "one weird trick" from Art of Computer Programming was how we allocated RAM for multiple concurrent applications.
- sgerenser 3y ago
  Pretty sure even with virtual memory (which was actually added sometime in the System 7 days), you still could manually set the minimum and desired memory sizes for each app. Maybe it made less of a difference than it used to, but I still remember tweaking those values for certain apps (like trying to open a large file in Photoshop) even after MacOS 8 and 9 were out. MacOS X was a breath of fresh air by comparison.
  - shadowgovt 3y ago
    You definitely could. I can't remember right now what effect that had, because the whole thing was running atop a virtual memory layer at that point... I can't recall if it was a lie (i.e. feature existed but had no effect) or if it had some effect on how long it'd be before an app started resorting to paging out RAM pages.
bewaretheirs 3y ago
> Have one array grow normally from location#0, and the second array grow backwards from location#End. The stack in most ISAs and ABIs grows down from a high address, allowing this trick to be used to divide memory flexibly between heap and stack in single-threaded small-memory systems.
yongjik 3y ago
> Have one array grow normally from location#0, and the second array grow backwards from location#End. Fun fact: Itanium had two stacks, one for manual push/pop and another for cycling through the register file. One stack grew upward, another grew downward. A fascinating architecture, though it never delivered the promised performance.
masfuerte 3y ago
Some word processors on 8-bit computers worked like this. Your document took all of the available RAM. Text before the cursor was at the start of RAM and text after the cursor was at the end of RAM. Insertions and pastes didn't need to shuffle data around but navigation did. It worked well.
- shadowgovt 3y ago
  emacs still does this IIUC. The beating heart of the emacs edit model is a "gap buffer" at the cursor. There's a neat compare-and-contrast someone did awhile back on the gap buffer approach vs. the other approach often taken for code IDEs ("ropes"). The tl;dr is that gap buffers are actually really performant for a lot of cases except for having to edit at a lot of randomly-chosen cursor points far apart from each other (but how often is that your use case?). https://coredumped.dev/2023/08/09/text-showdown-gap-buffers-vs-ropes/ https://coredumped.dev/2023/08/09/text-showdown-gap-buffers-...
  - cerved 3y ago
    seems like Vim does too
  - derefr 3y ago
    > except for having to edit at a lot of randomly-chosen cursor points far apart from each other (but how often is that your use case?) I use Sublime, and pretty often I do a "Find All" for some term; then Multiselect (Cmd+L); then select from cursor (Shift+RightArrow); and then type something. Which is essentially "editing at a lot of randomly [or at least arbitrarily]-chosen cursor points." That, and IIRC Sublime actually does its "Find and Replace All" operation, as essentially this same multicursor-select-and-type operation internally. (If you have a large-enough buffer open, you can see it gradually doing it!)
    - shadowgovt 3y ago
      I've never been able to make that work, but I respect that you have. Generally, that kind of select almost always grabs a bunch of substrings that aren't appropriate and I end up mangling my file.
fuzztester 3y ago
>but at that point you might as well use Malloc and Realloc. IIRC, the first edition of the classic K&R C book, The C Programming Language, had an example of creating a memory allocator and using it.
- tengwar2 3y ago
  It's not difficult to write a memory allocator, but there are some assumptions there which don't always hold true. For instance SmartCards (e.g. SIMs) use a language alleged to be Java, but without a garbage collector and with only one data type. Applications never terminate, so while you can allocate heap memory, you cannot free it and memory exhaustion is one way to brick the device. Since it is "Java" you don't have the low level control of C. Standard practice is to allocate some global variables once, and use them throughout the life of the device. Since another way to brick the device is by exhausting write cycles on the EEPROM on which these variables are stored, you are also allowed to allocate an array in the small amount of RAM. Ah, you might think - I can use that for an allocator! Nope. The array space is only allocated until the end of an event handler, and after that it holds undefined content.
  - fuzztester 3y ago
    Interesting. What data type?
dspillett 3y ago
> While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for dynamically changing arrays or other data structures. These are not as obsolete as they might seem to many. In some environments you might still be very restricted and want to avoid all dynamic allocation which could force you to use these types of algorithm so you can work in-place in a static memory block.

Retr0id 3y ago

SQLite's on-disk format uses a similar array technique for storing the contents of table btree leaf node pages. Within a fixed-size page, there's an array of offsets growing forwards, and an array of (variable length) row values growing backwards from the end - the latter of which may end up with holes when rows are deleted (iiuc). It wouldn't surprise me if it was a direct inspiration, since their docs cite TAOCP for the btree structure itself.

hiAndrewQuinn 3y ago
We know from the Corecursive podcast on the hidden story of SQLite that Dr. Hipp did indeed reference and pull at least one alg straight from Knuth's books, which he had behind his desk. What a different world that must have been!
- andrewshadura 3y ago
  FYI, he's D. R. Hipp, not Dr. Hipp.
  - jcgrillo 3y ago
    More like Dr. D. R. Hipp, actually.
    - tomcam 3y ago
      Hilarious and true
    - jeffrallen 3y ago
      Great rapper name.
  - deleted 3y ago
    [deleted]
felixge 3y ago
This sounds like it was copied from PostreSQL which SQLite cites as a strong source of inspiration.
tanelpoder 3y ago
Oracle does this as well and I suspect many other row-major RDBMS storage engines do too.
suncherta 3y ago
As others have already mentioned this is used in a lot (most?) of databases. It is called "slotted-page". Searching for it gives good discussions/explanations of it.

shadowgovt 3y ago

This succinctly describes how old MacOS allocated per-application resources. Each app had a minimum and preferred RAM requirement tagged to it. When launched, it would take up the whole preferred slot, unless that amount wasn't available in which case it'd take up less than preferred (and fail to launch if it couldn't get minimum). The system allocated the heap (and libraries, I think) at the bottom and the stack at the top of that physical-RAM slice, and off you went. I believe around system 8 they added a virtualization layer that started to obviate the need for that approach (and of course by the time of MacOSX they were using paged memory like everyone else was and so such fancy tap-dancing was no longer needed). But it's fun to think about the era where this "one weird trick" from Art of Computer Programming was how we allocated RAM for multiple concurrent applications.

sgerenser 3y ago
Pretty sure even with virtual memory (which was actually added sometime in the System 7 days), you still could manually set the minimum and desired memory sizes for each app. Maybe it made less of a difference than it used to, but I still remember tweaking those values for certain apps (like trying to open a large file in Photoshop) even after MacOS 8 and 9 were out. MacOS X was a breath of fresh air by comparison.
- shadowgovt 3y ago
  You definitely could. I can't remember right now what effect that had, because the whole thing was running atop a virtual memory layer at that point... I can't recall if it was a lie (i.e. feature existed but had no effect) or if it had some effect on how long it'd be before an app started resorting to paging out RAM pages.

bewaretheirs 3y ago

> Have one array grow normally from location#0, and the second array grow backwards from location#End. The stack in most ISAs and ABIs grows down from a high address, allowing this trick to be used to divide memory flexibly between heap and stack in single-threaded small-memory systems.

yongjik 3y ago

> Have one array grow normally from location#0, and the second array grow backwards from location#End. Fun fact: Itanium had two stacks, one for manual push/pop and another for cycling through the register file. One stack grew upward, another grew downward. A fascinating architecture, though it never delivered the promised performance.

masfuerte 3y ago

Some word processors on 8-bit computers worked like this. Your document took all of the available RAM. Text before the cursor was at the start of RAM and text after the cursor was at the end of RAM. Insertions and pastes didn't need to shuffle data around but navigation did. It worked well.

shadowgovt 3y ago
emacs still does this IIUC. The beating heart of the emacs edit model is a "gap buffer" at the cursor. There's a neat compare-and-contrast someone did awhile back on the gap buffer approach vs. the other approach often taken for code IDEs ("ropes"). The tl;dr is that gap buffers are actually really performant for a lot of cases except for having to edit at a lot of randomly-chosen cursor points far apart from each other (but how often is that your use case?). https://coredumped.dev/2023/08/09/text-showdown-gap-buffers-vs-ropes/ https://coredumped.dev/2023/08/09/text-showdown-gap-buffers-...
- cerved 3y ago
  seems like Vim does too
- derefr 3y ago
  > except for having to edit at a lot of randomly-chosen cursor points far apart from each other (but how often is that your use case?) I use Sublime, and pretty often I do a "Find All" for some term; then Multiselect (Cmd+L); then select from cursor (Shift+RightArrow); and then type something. Which is essentially "editing at a lot of randomly [or at least arbitrarily]-chosen cursor points." That, and IIRC Sublime actually does its "Find and Replace All" operation, as essentially this same multicursor-select-and-type operation internally. (If you have a large-enough buffer open, you can see it gradually doing it!)
  - shadowgovt 3y ago
    I've never been able to make that work, but I respect that you have. Generally, that kind of select almost always grabs a bunch of substrings that aren't appropriate and I end up mangling my file.

fuzztester 3y ago

>but at that point you might as well use Malloc and Realloc. IIRC, the first edition of the classic K&R C book, The C Programming Language, had an example of creating a memory allocator and using it.

tengwar2 3y ago
It's not difficult to write a memory allocator, but there are some assumptions there which don't always hold true. For instance SmartCards (e.g. SIMs) use a language alleged to be Java, but without a garbage collector and with only one data type. Applications never terminate, so while you can allocate heap memory, you cannot free it and memory exhaustion is one way to brick the device. Since it is "Java" you don't have the low level control of C. Standard practice is to allocate some global variables once, and use them throughout the life of the device. Since another way to brick the device is by exhausting write cycles on the EEPROM on which these variables are stored, you are also allowed to allocate an array in the small amount of RAM. Ah, you might think - I can use that for an allocator! Nope. The array space is only allocated until the end of an event handler, and after that it holds undefined content.
- fuzztester 3y ago
  Interesting. What data type?

dspillett 3y ago

> While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for dynamically changing arrays or other data structures. These are not as obsolete as they might seem to many. In some environments you might still be very restricted and want to avoid all dynamic allocation which could force you to use these types of algorithm so you can work in-place in a static memory block.