Hacker News Reader

Comment by dragontamer | Hacker News Reader

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.

View on HN

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.

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-...

> 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!)

I’ve never noticed any perceptible latency using iedit[1] in Emacs, which does what it sounds to me like you are describing.

It does suggest a possible multigap buffer structure though for efficiently doing simultaneous edits of distant locations in very large files. In that case though I’d probably be iediting a small wgrep[2] buffer anyhow so it might not really matter.

[1] https://github.com/victorhge/iedit

[2] https://github.com/mhayashi1120/Emacs-wgrep

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.

I do the same thing in sublime. Doing it still feels like I have super powers even after years of doing it.

I’m sure there’s some magic key combo in emacs and/or vim to do it, too.

seems like Vim does too

> 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.

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.

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.

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.

> 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.

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.

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!

FYI, he's D. R. Hipp, not Dr. Hipp.

More like Dr. D. R. Hipp, actually.

Great rapper name.

Hilarious and true

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.

This sounds like it was copied from PostreSQL which SQLite cites as a strong source of inspiration.

Oracle does this as well and I suspect many other row-major RDBMS storage engines do too.

> 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.

>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.

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.

Interesting. What data type?

Reply on news.ycombinator.com