Am I the only one who read it as the ancient world before computers existed had stacks or heaps? English is so weird sometimes...
I’m no grammarian but I think it should have a comma after “world”.
Subroutine calls in the ancient world, before computers had stacks or heaps
21–30 of 241 posts
Re: Subroutine calls in the ancient world, before computers had stacks or heaps
#22I 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 ta…
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 fo…
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!
Re: Subroutine calls in the ancient world, before computers had stacks or heaps
#23"There was just one catch: You can't do recursion." You could do tail recursion, because only the return address of the first call would be needed to be stored. `branch_with_link` would be used for the initial call, but the recursive calls would have to be regular branches.
Most recursion is about as bad as goto coding methodologies.
Personally, I think it should be avoided in modern compiled languages too.
Haskell is fun to play around on, but it is horrific to consider using in a stable production environment. =)
Re: Subroutine calls in the ancient world, before computers had stacks or heaps
#24"There was just one catch: You can't do recursion." You could do tail recursion, because only the return address of the first call would be needed to be stored. `branch_with_link` would be used for the initial call, but the recursive calls would have to be regular branches.
Most recursion is about as bad as goto coding methodologies. Personally, I think it should be avoided in modern compiled languages too. Haskell is fun to play around on, but it is horrific to consider using in a stable production environment. =)
Outside of a university course, if I see recursion in a non-FP language I consider it a code-smell
Re: Subroutine calls in the ancient world, before computers had stacks or heaps
#25I 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 ta…
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 fo…
This sounds like it was copied from PostreSQL which SQLite cites as a strong source of inspiration.
Re: Subroutine calls in the ancient world, before computers had stacks or heaps
#26If you write a GPU shader in most graphics APIs today you will also not have a stack or heap.
Re: Subroutine calls in the ancient world, before computers had stacks or heaps
#27[deleted]
Re: Subroutine calls in the ancient world, before computers had stacks or heaps
#28I 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 ta…
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.
Re: Subroutine calls in the ancient world, before computers had stacks or heaps
#29Note that before we had arbitrarily extensible heaps, programmers always did at least a little engineering, in that they had to consider the probable distribution of inputs and size* all their intermediate storage appropriately. * giving rise to "BUGS AND LIMITATIONS "
Those before times are still today, depending on what you're doing. For hard real-time, dynamic memory is (almost) never used, mostly because the time needed to alloc/free memory isn't deterministic. So everything is statically allocated at compile time and yeah, you've got to know how much memory your inputs are going to consume. But knowing the bounds of memory consumption used to be normal for application programm…
> What do people do now, just YOLO memory usage?
Yes, literally. Careful allocation has given way to "Use what's there and fail hard if it ain't enough" in the era where machines are cheap and the dominant paradigm is how parallel you can make your algorithm so you can solve your problem with scale.
In the modern era, for most online service software (which is, I'd argue, most software people interface with these days), you write it as fast as you can, prototype it small, start to care about RAM allocation (but build it to just die screaming if it runs out of RAM so you know you need to make a change), and keep scaling up.
You don't care a lot about RAM allocation until you're scaled to a lot of nodes because only at that scale is whether the app takes up a kilobyte less going to start to matter on machines that are swinging gigabytes of storage around.
There are plenty of application spaces where this isn't the status quo (embedded architectures, console gaming), but that tends to be considered specialist engineering in this day and age.
Re: Subroutine calls in the ancient world, before computers had stacks or heaps
#30I 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 ta…
> 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.