12 ms·

The memory models that underlie programming languages (2016)

304 points by signa11 5y ago

gumby 5y ago
Wow, I'm surprised I never ran across this excellent essay before. I also liked the use of the term "memory model" in this case to mean conceptual model, because the metaphors and affordances of a language are what give (or restrict) its expressive power and the level of abstraction you can bring to bear. A mixed blessing.
- kragen 5y ago
  Thanks, that means a lot! I think it kind of falls short of some of its initial promises, and clearly needs revision, but there are some good nuggets in there. As one example of what needs revision, I drew the diagrams after I wrote the text, and I realized that what I was describing in the text was far more complicated than what I really wanted to draw... but then never went back and revised the text. If this is the kind of thing you like, you might find more things to your taste in http://canonical.org/~kragen/dercuano http://canonical.org/~kragen/dercuano, which touches on, among other things, the bizarre memory model of the Zork Z-machine.
  - zestyping 5y ago
    Hi, Kragen! Is Dercuano available as individual HTML pages that can be clicked around (and indexed by search engines)? So far I've only found it as a giant blob (PDF or tar) and I'm wondering why that seems to be its primary presentation.
    - kragen 5y ago
      Hi Ping! I miss you a lot! The primary representation of Dercuano is a giant blob both to improve the chances that copies of it will survive after I'm dead and to more clearly establish a publication date for purposes of patent prior art. The PDF isn't very good (I hacked together a PDF-rendering script with reportlab in five days before the deadline, and even the CSS for the HTML version is pretty amateurish) but there are a variety of places that can view or archive PDFs but not tarballs of HTML. There's also an online mirror at https://dercuano.github.io/ https://dercuano.github.io/, which allows linking to pages like https://dercuano.github.io/topics/memory-models.html https://dercuano.github.io/topics/memory-models.html, but of course that depends on Microsoft's pleasure. See also http://canonical.org/~kragen/derctuo/ http://canonical.org/~kragen/derctuo/ for the sequel.
  - silentsea90 5y ago
    No offense but I do agree that the text is hard to read and understand and simpler sentences would be nicer.
    - kragen 5y ago
      I have that problem a lot.
      - danielmarkbruce 5y ago
        This book is (imo) hilariously good and explains thing well for engineering type folks: https://www.amazon.com/Sense-Style-Thinking-Persons-Writing-ebook/dp/B00INIYG74 https://www.amazon.com/Sense-Style-Thinking-Persons-Writing-...
  - fjfaase 5y ago
    Hi Kragen, for a long time, I have been pondenring about a high-level 'programming' languages about structured data. It is by far finished, but I am attempting to deal with the problem of different memory models from the other end: starting with an ideal model trying to abstract from implementations. I have not address the problem of transactions and cooperation yet. Often the problem with implementation of data models start becoming 'interesting' when several actors at the same time are querying and changing it, especially when the dimension of distribution is added. https://github.com/FransFaase/DataLang https://github.com/FransFaase/DataLang
    - kragen 5y ago
      This is fascinating! It looks like it's inspired by linear (or affine?) typing, but isn't quite the same thing? It's definitely true that concurrency is a common source of such complications. Serialization is another one.
  - Cybotron5000 5y ago
    I’m only about half way through, but I’m finding it extremely helpful, clear and well-written (some of the terminology/ideas I’m not familiar with/are over my head, but I plan on going back over it again later and looking stuff up :) - Thanks so much!
    - kragen 5y ago
      Maybe the stuff that seems over your head is just stuff I wrote poorly!
      - tekknolagi 5y ago
        This is a great teaching attitude. Thank you.
        kragen 5y ago
        Maybe if I keep trying I'll get good at teaching some day! So far my results have not been inspiring.
      - Cybotron5000 5y ago
        Not at all! I’m obviously not qualified to say, but it seems to me to be a great overview of a very complicated topic - clear, concise, comprehensive and not patronising. Stuff I don’t understand off the bat I can always look up, but it gives me a framework to begin to hang stuff on/explore from. Even if you had written several tome-like textbooks you couldn’t have compensated for my ignorance of the basic principles of computer science/informatics/programming etc.! :)
- jcranmer 5y ago
  As a compiler writer, when I hear the term "memory model", I immediately assume it's referring to a multithreaded memory model, and is going to discuss when writes are guaranteed to be made visible to other threads. A better term for what's discussed here would be the "object model"--you're effectively describing how you would represent a conceptual object in different memory organization schemes.
  - kragen 5y ago
    Yeah, "memory model" is a terribly overloaded term (myself, I think small, compact, medium, large, huge), and "object model" has the same problem. Maybe I should just generate a random neologism.
    - gumby 5y ago
      In this case I liked this particular overloading of the term because it caused me to reset certain assumptions.
  - Animats 5y ago
    Yes. But we mostly have one memory model today - one big flat memory space, because C. There are other approaches, but most of the clever ones died off. x86-32 has lots of interesting things you can do with segments. Nobody used that stuff, so amd64 has flat memory. Burroughs once had a memory system that worked like pathnames. Think of an address as being "job/program/module/function/variable[n]", not a number. User programs could not see the physical memory address. This allowed the OS to do swapping and compaction underneath the program. The hardware would catch subscripting out of range. Worked fine, never caught on. Today we do that with collection classes, rather than at the OS/hardware level. Memory models are making a comeback, as we hit the limits of caches. Machines with some memory shared, some memory unshared, and some slower if shared have appeared.
    - kaba0 5y ago
      This topic is outside the realm of my knowledge, but at the language level, we do have that (compacting GCs), and I think we do have it at the OS level as well due to virtual memory (but hardware accelerated TLB).
ChrisArchitect 5y ago
(2016)
- dang 5y ago
  Added. Thanks!
ChrisArchitect 5y ago
previous discussions: 3 years ago, https://news.ycombinator.com/item?id=17099608 https://news.ycombinator.com/item?id=17099608 4 years ago, https://news.ycombinator.com/item?id=13293290 https://news.ycombinator.com/item?id=13293290
- vitiral 5y ago
  I'm glad this was reposted. An excellent read that I had not seen before.
  - kragen 5y ago
    I'm glad you're enjoying it!
drivers99 5y ago
So the "program Fortran in any language" (using only arrays as illustrated in the linked paper[1]) is interesting. I didn't know it was called that since I didn't learn Fortran. (I just flashed back to a memory of someone I worked with around 2000 who said he wrote Fortran in Perl.) Once, I was in a hurry to write a Tetris clone using pygame library, and was just starting to learn Python, so I read just enough of the Python tutorial to get started (but didn't get to classes) and then wrote it without any classes (structures), and just used all parallel arrays instead. It reminded me of the way I originally learned to write text adventures in Basic (from a short book in the 80s about how to do that, by Christopher Lampton).[2] I've been interested in Forth lately, so it was interesting to see him bring that up as well. [1] See section 5 of the linked paper: http://www.the-adam.com/adam/rantrave/st02.pdf http://www.the-adam.com/adam/rantrave/st02.pdf [2] See chapter 4 of that book for example: https://archive.org/details/how-to-create-adventure-games/page/n37/mode/2up https://archive.org/details/how-to-create-adventure-games/pa...
Animats 5y ago
Rust has an interesting, and somewhat difficult, memory model. First, there's the single ownership tree. Single ownership is checked by the borrow checker. You can have only one mutable reference to a data object at a time, and that's also checked by the borrow checker. If you can stay within that model, if the program compiles, it will probably work at the data access level. But then there are all the escape hatches. There's "Rc", which is reference counting for read-only use. This works fine for immutable objects, but not for mutable ones. There's "Cell" and "RefCell". These allow multiple ownership, and only one mutable access at a time. Request mutable access via two routes and you get a panic, or an error if you use try_borrow(); The static analysis of the borrow checker is not able to figure out when you're headed for trouble via this route. There's "Arc" and "Mutex", which allows access across thread boundaries. Request access via two routes in the same thread, and you deadlock. Designing the data structures for something tightly coupled with concurrency, like a window manager or a game, is difficult.
- pkolaczk 5y ago
  > The static analysis of the borrow checker is not able to figure out when you're headed for trouble via this route. This route exists purely because you can't statically prove some programs correct. Without it, the compiler would have to reject some correct programs and the language would be more limited. This is unfair to complain about it when the GC-based alternatives push all of memory management to runtime, so the surface for getting panics is a lot larger. Rust's solution is not perfect but still the best you can get. > Designing the data structures for something tightly coupled with concurrency, like a window manager or a game, is difficult. It is difficult in any language. The difference is that in Rust you face that difficulty when trying to design/compile your program, and in other more permissive languages you face it when your customer reports a bug. The cost of fixing problems is lowest when they are detected early, so Rust has a clear edge here.
  - alxlaz 5y ago
    I'm not sure someone (including OP) would be "complaining" about it, considering that "this enforces borrow checker rules at runtime" is like the first or second thing in the documentation for RefCell and friends. The frustrating bit about it is not that you get panics or deadlocks at runtime, that is to be expected when you can't get them at compile time, after all. The nasty bit is that this memory model makes it very difficult to work with tightly-coupled, concurrent state, and you have to go through all the RefCell<Rc<Whatever>> escape hatches, at which point you're not that far from C++ hell (edit: i.e. you "pay extra", in the form of the awkward escape hatches, to get not that far from where you were before). In theory (or, if we're being realistic, in introductory tutorials) it's possible to avoid the escape hatches if you are careful to structure access to your data juuuuust right. That works out fine if you're the only person working on an infrequently-changing program with a small model that you understand very well. If everyone needs to hook into the first two or three function call levels of the main loop, and if your model is anything but small, that doesn't work out anymore. Six weeks into the whole thing and people spend more time un-breaking builds than writing code. Also, seriously, not every comment that says "I wish Rust did X better" is a wanton attack upon the technological excellence and purity of the one perfect language to rule them all...
klik99 5y ago
The "pipes" has some better examples - Lucid is a fantastic example. My own programming language Intonal (https://intonal.io/text https://intonal.io/text) is a practical continuation of Lucids ideas, in the first steps of seeing production use, combined with a "Haskell-lite" type system (control structures, typeclasses, second order functions, custom data types/enums, etc) - Turns out the "pipes" or data flow approach works really well for audio, also turns out there was/is a lot of to figure out about how memory works in such a language.
juloo 5y ago
The "lisp" section seems to conflate "object graphs" and object-oriented programming. It talks about classes while talking about garbage collection and before mentioning "object-oriented". Lisps, Haskell and ML have different model than the other languages in the list and don't have classes, objects are usually arrays of pointers with no special fields. Also, hash tables are usually implemented inside the language.
bruce343434 5y ago
> COBOL-derived languages like C and Golang give the garbage collector an easier time > C [...] garbage collector Excuse me?
- chakkepolja 5y ago
  Plug-in GCs like Boehm I guess.
- kragen 5y ago
  You're one of today's lucky ten thousand! https://www.hboehm.info/gc/ https://www.hboehm.info/gc/
allenbrunson 5y ago
i am going to echo a lot of the comments here and say that this is an eye-opening essay. it got me to thinking things that i would not have otherwise. that is a very high bar to clear, which very rarely happens. for any random bit of text on the internet you might choose to read, you can't expect much more than that. in that respect, it is a wild success. on the other hand ... i believe kragen has deep knowledge of this concept he's brought up, but he has failed to convey its specifics to people who don't already understand it. i acknowledge i may well be too stupid to grasp all this, but it would have been a nice bonus if i could have. i often wonder: why does any reasonably worthwhile program, the type other people will pay for, always require at least 50,000 lines of code? is that really necessary? surely we can do better than that. but if there's a way, apparently nobody has found it yet. i hope people like kragen help push the state of the art forward, so we might someday find a way around that.
- simiones 5y ago
  > i often wonder: why does any reasonably worthwhile program, the type other people will pay for, always require at least 50,000 lines of code? is that really necessary? surely we can do better than that. but if there's a way, apparently nobody has found it yet. i hope people like kragen help push the state of the art forward, so we might someday find a way around that. It's unlikely you'll get many people to pay for automating a simple process, so "serious programs" will generally only be the ones that automate complicated processes. So from the start, the pure algorithm you're going to implement will usually be complex. Then, to actually implement that algorithm on a real machine, you'll have to deal with all of the specifics of that machine as well, which adds significant boiler-plate even when coding in Python or Haskell, not to mention programming in C++ or Rust. This boilerplate typically grows exponentially with the size of the algorithm you have to implement, and with the size of the data that will be processed. It's also important to remember that many "simple" operations, such as "print the date one hour from now", or "read the user's name" hide huge complexity encoded in human context and history.
  - allenbrunson 5y ago
    > It's also important to remember that many "simple" operations, such as "print the date one hour from now", or "read the user's name" hide huge complexity encoded in human context and history. obviously true. but are those operations more complex than, say, what a modern cpu does? think of the effectively infinite number of details of computation that the cpu i am using to type this message is hiding from me. i don't need to know. it's all taken care of. but for some reason, we can't embed "print the date one hour from now" into the operating system, so that particular bit of code only has to be written once and then reused infinitely, like my cpu's microcode? programmers know why this is harder than it looks, of course. but is it really unsolvable? i hope not.
tutfbhuf 5y ago
This website does not support HTTPS.
jscipione 5y ago
This part struck me as odd: “… from McCarthy’s discovery of Lisp in 1959 until Lieberman and Hewitt’s discovery of generational garbage collection in 1980…”. Does the author really believe that Lisp (and garbage collection) was created by God (or an analog for God i.e. Nature) and was discovered by McCarthy? Lisp is a human invention not some immortal mathematical principle.
deleted 5y ago
[deleted]
ncmncm 5y ago
"Memory model" has yet a third meaning, referring to interference between operations in multiple CPU cores, and mediated by variously-shared parts of cache systems of varying complexity. Here, complexity of the memory model is traded off against complexity of the primitives to manage the interference, (compare-and-set, load-locked/store conditional, etc.) and with the complexity of the cache system. Java's original memory model, perhaps the first formally specified, turned out to be unimplementable on common actual machines. The next language to get a formal memory model was C++, followed shortly by C and then others. Real multicore machines have sorted themselves out into two models of cache coherency; one more forgiving represented by mainstream x86 and now Apple M1, relying on deeply complex cache designs, and the other by the remaining lottery survivors, non-Apple ARM, and Power. The various RISC-V implementations will probably straddle the divide, like ARM/ARM-M1. Java, C++, and C can with some discipine be coded to work transparently on either, but very often programs accidentally depend on the x86/Apple model, never having been tested beyond it. Rust, absent "unsafe", is happy on either. The Linux kernel works on either, and once supported other more exotic variations.

304 points by signa11 5y ago

Wow, I'm surprised I never ran across this excellent essay before. I also liked the use of the term "memory model" in this case to mean conceptual model, because the metaphors and affordances of a language are what give (or restrict) its expressive power and the level of abstraction you can bring to bear. A mixed blessing.

kragen 5y ago
Thanks, that means a lot! I think it kind of falls short of some of its initial promises, and clearly needs revision, but there are some good nuggets in there. As one example of what needs revision, I drew the diagrams after I wrote the text, and I realized that what I was describing in the text was far more complicated than what I really wanted to draw... but then never went back and revised the text. If this is the kind of thing you like, you might find more things to your taste in http://canonical.org/~kragen/dercuano http://canonical.org/~kragen/dercuano, which touches on, among other things, the bizarre memory model of the Zork Z-machine.
- zestyping 5y ago
  Hi, Kragen! Is Dercuano available as individual HTML pages that can be clicked around (and indexed by search engines)? So far I've only found it as a giant blob (PDF or tar) and I'm wondering why that seems to be its primary presentation.
  - kragen 5y ago
    Hi Ping! I miss you a lot! The primary representation of Dercuano is a giant blob both to improve the chances that copies of it will survive after I'm dead and to more clearly establish a publication date for purposes of patent prior art. The PDF isn't very good (I hacked together a PDF-rendering script with reportlab in five days before the deadline, and even the CSS for the HTML version is pretty amateurish) but there are a variety of places that can view or archive PDFs but not tarballs of HTML. There's also an online mirror at https://dercuano.github.io/ https://dercuano.github.io/, which allows linking to pages like https://dercuano.github.io/topics/memory-models.html https://dercuano.github.io/topics/memory-models.html, but of course that depends on Microsoft's pleasure. See also http://canonical.org/~kragen/derctuo/ http://canonical.org/~kragen/derctuo/ for the sequel.
- silentsea90 5y ago
  No offense but I do agree that the text is hard to read and understand and simpler sentences would be nicer.
  - kragen 5y ago
    I have that problem a lot.
    - danielmarkbruce 5y ago
      This book is (imo) hilariously good and explains thing well for engineering type folks: https://www.amazon.com/Sense-Style-Thinking-Persons-Writing-ebook/dp/B00INIYG74 https://www.amazon.com/Sense-Style-Thinking-Persons-Writing-...
- fjfaase 5y ago
  Hi Kragen, for a long time, I have been pondenring about a high-level 'programming' languages about structured data. It is by far finished, but I am attempting to deal with the problem of different memory models from the other end: starting with an ideal model trying to abstract from implementations. I have not address the problem of transactions and cooperation yet. Often the problem with implementation of data models start becoming 'interesting' when several actors at the same time are querying and changing it, especially when the dimension of distribution is added. https://github.com/FransFaase/DataLang https://github.com/FransFaase/DataLang
  - kragen 5y ago
    This is fascinating! It looks like it's inspired by linear (or affine?) typing, but isn't quite the same thing? It's definitely true that concurrency is a common source of such complications. Serialization is another one.
- Cybotron5000 5y ago
  I’m only about half way through, but I’m finding it extremely helpful, clear and well-written (some of the terminology/ideas I’m not familiar with/are over my head, but I plan on going back over it again later and looking stuff up :) - Thanks so much!
  - kragen 5y ago
    Maybe the stuff that seems over your head is just stuff I wrote poorly!
    - tekknolagi 5y ago
      This is a great teaching attitude. Thank you.
      - kragen 5y ago
        Maybe if I keep trying I'll get good at teaching some day! So far my results have not been inspiring.
    - Cybotron5000 5y ago
      Not at all! I’m obviously not qualified to say, but it seems to me to be a great overview of a very complicated topic - clear, concise, comprehensive and not patronising. Stuff I don’t understand off the bat I can always look up, but it gives me a framework to begin to hang stuff on/explore from. Even if you had written several tome-like textbooks you couldn’t have compensated for my ignorance of the basic principles of computer science/informatics/programming etc.! :)
jcranmer 5y ago
As a compiler writer, when I hear the term "memory model", I immediately assume it's referring to a multithreaded memory model, and is going to discuss when writes are guaranteed to be made visible to other threads. A better term for what's discussed here would be the "object model"--you're effectively describing how you would represent a conceptual object in different memory organization schemes.
- kragen 5y ago
  Yeah, "memory model" is a terribly overloaded term (myself, I think small, compact, medium, large, huge), and "object model" has the same problem. Maybe I should just generate a random neologism.
  - gumby 5y ago
    In this case I liked this particular overloading of the term because it caused me to reset certain assumptions.
- Animats 5y ago
  Yes. But we mostly have one memory model today - one big flat memory space, because C. There are other approaches, but most of the clever ones died off. x86-32 has lots of interesting things you can do with segments. Nobody used that stuff, so amd64 has flat memory. Burroughs once had a memory system that worked like pathnames. Think of an address as being "job/program/module/function/variable[n]", not a number. User programs could not see the physical memory address. This allowed the OS to do swapping and compaction underneath the program. The hardware would catch subscripting out of range. Worked fine, never caught on. Today we do that with collection classes, rather than at the OS/hardware level. Memory models are making a comeback, as we hit the limits of caches. Machines with some memory shared, some memory unshared, and some slower if shared have appeared.
  - kaba0 5y ago
    This topic is outside the realm of my knowledge, but at the language level, we do have that (compacting GCs), and I think we do have it at the OS level as well due to virtual memory (but hardware accelerated TLB).

ChrisArchitect 5y ago

(2016)

dang 5y ago
Added. Thanks!

ChrisArchitect 5y ago

previous discussions: 3 years ago, https://news.ycombinator.com/item?id=17099608 https://news.ycombinator.com/item?id=17099608 4 years ago, https://news.ycombinator.com/item?id=13293290 https://news.ycombinator.com/item?id=13293290

vitiral 5y ago
I'm glad this was reposted. An excellent read that I had not seen before.
- kragen 5y ago
  I'm glad you're enjoying it!

drivers99 5y ago

So the "program Fortran in any language" (using only arrays as illustrated in the linked paper[1]) is interesting. I didn't know it was called that since I didn't learn Fortran. (I just flashed back to a memory of someone I worked with around 2000 who said he wrote Fortran in Perl.) Once, I was in a hurry to write a Tetris clone using pygame library, and was just starting to learn Python, so I read just enough of the Python tutorial to get started (but didn't get to classes) and then wrote it without any classes (structures), and just used all parallel arrays instead. It reminded me of the way I originally learned to write text adventures in Basic (from a short book in the 80s about how to do that, by Christopher Lampton).[2] I've been interested in Forth lately, so it was interesting to see him bring that up as well. [1] See section 5 of the linked paper: http://www.the-adam.com/adam/rantrave/st02.pdf http://www.the-adam.com/adam/rantrave/st02.pdf [2] See chapter 4 of that book for example: https://archive.org/details/how-to-create-adventure-games/page/n37/mode/2up https://archive.org/details/how-to-create-adventure-games/pa...

Animats 5y ago

Rust has an interesting, and somewhat difficult, memory model. First, there's the single ownership tree. Single ownership is checked by the borrow checker. You can have only one mutable reference to a data object at a time, and that's also checked by the borrow checker. If you can stay within that model, if the program compiles, it will probably work at the data access level. But then there are all the escape hatches. There's "Rc", which is reference counting for read-only use. This works fine for immutable objects, but not for mutable ones. There's "Cell" and "RefCell". These allow multiple ownership, and only one mutable access at a time. Request mutable access via two routes and you get a panic, or an error if you use try_borrow(); The static analysis of the borrow checker is not able to figure out when you're headed for trouble via this route. There's "Arc" and "Mutex", which allows access across thread boundaries. Request access via two routes in the same thread, and you deadlock. Designing the data structures for something tightly coupled with concurrency, like a window manager or a game, is difficult.

pkolaczk 5y ago
> The static analysis of the borrow checker is not able to figure out when you're headed for trouble via this route. This route exists purely because you can't statically prove some programs correct. Without it, the compiler would have to reject some correct programs and the language would be more limited. This is unfair to complain about it when the GC-based alternatives push all of memory management to runtime, so the surface for getting panics is a lot larger. Rust's solution is not perfect but still the best you can get. > Designing the data structures for something tightly coupled with concurrency, like a window manager or a game, is difficult. It is difficult in any language. The difference is that in Rust you face that difficulty when trying to design/compile your program, and in other more permissive languages you face it when your customer reports a bug. The cost of fixing problems is lowest when they are detected early, so Rust has a clear edge here.
- alxlaz 5y ago
  I'm not sure someone (including OP) would be "complaining" about it, considering that "this enforces borrow checker rules at runtime" is like the first or second thing in the documentation for RefCell and friends. The frustrating bit about it is not that you get panics or deadlocks at runtime, that is to be expected when you can't get them at compile time, after all. The nasty bit is that this memory model makes it very difficult to work with tightly-coupled, concurrent state, and you have to go through all the RefCell<Rc<Whatever>> escape hatches, at which point you're not that far from C++ hell (edit: i.e. you "pay extra", in the form of the awkward escape hatches, to get not that far from where you were before). In theory (or, if we're being realistic, in introductory tutorials) it's possible to avoid the escape hatches if you are careful to structure access to your data juuuuust right. That works out fine if you're the only person working on an infrequently-changing program with a small model that you understand very well. If everyone needs to hook into the first two or three function call levels of the main loop, and if your model is anything but small, that doesn't work out anymore. Six weeks into the whole thing and people spend more time un-breaking builds than writing code. Also, seriously, not every comment that says "I wish Rust did X better" is a wanton attack upon the technological excellence and purity of the one perfect language to rule them all...

klik99 5y ago

The "pipes" has some better examples - Lucid is a fantastic example. My own programming language Intonal (https://intonal.io/text https://intonal.io/text) is a practical continuation of Lucids ideas, in the first steps of seeing production use, combined with a "Haskell-lite" type system (control structures, typeclasses, second order functions, custom data types/enums, etc) - Turns out the "pipes" or data flow approach works really well for audio, also turns out there was/is a lot of to figure out about how memory works in such a language.

juloo 5y ago

The "lisp" section seems to conflate "object graphs" and object-oriented programming. It talks about classes while talking about garbage collection and before mentioning "object-oriented". Lisps, Haskell and ML have different model than the other languages in the list and don't have classes, objects are usually arrays of pointers with no special fields. Also, hash tables are usually implemented inside the language.

bruce343434 5y ago

> COBOL-derived languages like C and Golang give the garbage collector an easier time > C [...] garbage collector Excuse me?

chakkepolja 5y ago
Plug-in GCs like Boehm I guess.
kragen 5y ago
You're one of today's lucky ten thousand! https://www.hboehm.info/gc/ https://www.hboehm.info/gc/

allenbrunson 5y ago

i am going to echo a lot of the comments here and say that this is an eye-opening essay. it got me to thinking things that i would not have otherwise. that is a very high bar to clear, which very rarely happens. for any random bit of text on the internet you might choose to read, you can't expect much more than that. in that respect, it is a wild success. on the other hand ... i believe kragen has deep knowledge of this concept he's brought up, but he has failed to convey its specifics to people who don't already understand it. i acknowledge i may well be too stupid to grasp all this, but it would have been a nice bonus if i could have. i often wonder: why does any reasonably worthwhile program, the type other people will pay for, always require at least 50,000 lines of code? is that really necessary? surely we can do better than that. but if there's a way, apparently nobody has found it yet. i hope people like kragen help push the state of the art forward, so we might someday find a way around that.

simiones 5y ago
> i often wonder: why does any reasonably worthwhile program, the type other people will pay for, always require at least 50,000 lines of code? is that really necessary? surely we can do better than that. but if there's a way, apparently nobody has found it yet. i hope people like kragen help push the state of the art forward, so we might someday find a way around that. It's unlikely you'll get many people to pay for automating a simple process, so "serious programs" will generally only be the ones that automate complicated processes. So from the start, the pure algorithm you're going to implement will usually be complex. Then, to actually implement that algorithm on a real machine, you'll have to deal with all of the specifics of that machine as well, which adds significant boiler-plate even when coding in Python or Haskell, not to mention programming in C++ or Rust. This boilerplate typically grows exponentially with the size of the algorithm you have to implement, and with the size of the data that will be processed. It's also important to remember that many "simple" operations, such as "print the date one hour from now", or "read the user's name" hide huge complexity encoded in human context and history.
- allenbrunson 5y ago
  > It's also important to remember that many "simple" operations, such as "print the date one hour from now", or "read the user's name" hide huge complexity encoded in human context and history. obviously true. but are those operations more complex than, say, what a modern cpu does? think of the effectively infinite number of details of computation that the cpu i am using to type this message is hiding from me. i don't need to know. it's all taken care of. but for some reason, we can't embed "print the date one hour from now" into the operating system, so that particular bit of code only has to be written once and then reused infinitely, like my cpu's microcode? programmers know why this is harder than it looks, of course. but is it really unsolvable? i hope not.

tutfbhuf 5y ago

This website does not support HTTPS.

jscipione 5y ago

This part struck me as odd: “… from McCarthy’s discovery of Lisp in 1959 until Lieberman and Hewitt’s discovery of generational garbage collection in 1980…”. Does the author really believe that Lisp (and garbage collection) was created by God (or an analog for God i.e. Nature) and was discovered by McCarthy? Lisp is a human invention not some immortal mathematical principle.

deleted 5y ago

[deleted]

ncmncm 5y ago

"Memory model" has yet a third meaning, referring to interference between operations in multiple CPU cores, and mediated by variously-shared parts of cache systems of varying complexity. Here, complexity of the memory model is traded off against complexity of the primitives to manage the interference, (compare-and-set, load-locked/store conditional, etc.) and with the complexity of the cache system. Java's original memory model, perhaps the first formally specified, turned out to be unimplementable on common actual machines. The next language to get a formal memory model was C++, followed shortly by C and then others. Real multicore machines have sorted themselves out into two models of cache coherency; one more forgiving represented by mainstream x86 and now Apple M1, relying on deeply complex cache designs, and the other by the remaining lottery survivors, non-Apple ARM, and Power. The various RISC-V implementations will probably straddle the divide, like ARM/ARM-M1. Java, C++, and C can with some discipine be coded to work transparently on either, but very often programs accidentally depend on the x86/Apple model, never having been tested beyond it. Rust, absent "unsafe", is happy on either. The Linux kernel works on either, and once supported other more exotic variations.