6 ms·

One of the advantages of this kind of architecture is that if one reader is reading the old tree while it is replaced, it just works. Databases are really good

by btilly 3y ago

One of the advantages of this kind of architecture is that if one reader is reading the old tree while it is replaced, it just works. Databases are really good at having multiple versions of the same data structure be accessible at the same time. I hand rolled some similar data structures in higher order languages when I couldn't find any Python packages that gave me the same capability. But I couldn't figure out what a good name would be for, say, a dictionary that could have multiple concurrent versions. So I never went anything where with that.

Hnrobert42 3y ago
As Phil Karlton, “There are only two hard things in computer science: cache validation and naming things.” Seems like you found a way to work on both! https://skeptics.stackexchange.com/questions/19836/has-phil-karlton-ever-said-there-are-only-two-hard-things-in-computer-science#39178 https://skeptics.stackexchange.com/questions/19836/has-phil-...
- timeimp 3y ago
  I always have to add the "and off-by-one" at the end. Nothing like reading memory you don't own!
  - airstrike 3y ago
    There are actually only two hard problems in computer science: 0) Cache invalidation 1) Naming things 5) Asynchronous callbacks 2) Off-by-one errors 3) Scope creep 6) Bounds checking
    - alternative_a 3y ago
      Let’s be pedantic here and get all religious over the words “Science” and “hard”. Computer “science” has a difficult conceptual problem with caching. The optimal cache, this science tells us, is indistinguishable from a fortune teller who is never wrong (oracle). Fortune telling is a “hard” problem for a science based on reasoning. The best we can do is hedge bets (which is what the science of caching focuses on). This same science also has a difficulty with naming things. Now numbering things is easy and science loves maths and maths love sciences, but science and letters have a more difficult history. Science would approve of “factoryfactoryfactoryImpl” btw ... it’s “a rational scheme of naming”. . Here we see a “science” that is facing actual difficulties. The rest of your list are difficult but not “hard”. The science of these matters is clear and the rest is up to the “scientists” struggling with “scope creep” and “bounds checking” ..
    - Scarblac 3y ago
      There is only one hard problem in software engineering: people.
- pmarreck 3y ago
  invalidation?
  - Hnrobert42 3y ago
    Yes. Stupid speech to text and I didn’t double check. Thanks.
j-pb 3y ago
These things are usually called "persistent" versions of the thing, e.g. persistent Dictionary. Sometimes "immutably persistent" to distinguish it from the "durable" meaning of persistence i.e. written to disk.
- btilly 3y ago
  It seems odd to me to call a data structure "persistent" when its purpose is to allow you to cheaply keep many similar transitory copies around until you throw them away. The specific application was using dynamic programming to build up a complex data structure. You wind up with many copies of very similar data structures, and doing a deep copy each time is prohibitively expensive.
  - ncruces 3y ago
    Still that's what they're called: https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure Precisely because previous versions remain valid (persist) under modification.
    - btilly 3y ago
      There is a key difference between that, and what I created. The difference is that persistent data structures allow you to traverse the history of the data structure to find past versions. By contrast I only allowed you to see the current version, returning a new version of the root any time you made a modification. As a result, the memory associated with the old version could be freed once nothing would want to access it again. And any version that you had could still be manipulated. For the example that I was dealing with, both made sense. On top of that it made it possible to create a hashable version of the data structure that had a good chance (not a guarantee) of matching hashes when you arrived at the same data structure through different histories.
      - ncruces 3y ago
        Well, the difference isn't that great. You wrote: “the memory associated with the old version could be freed once nothing would want to access it again.” So all it really takes is something wanting.

by btilly 3y ago

Hnrobert42 3y ago

As Phil Karlton, “There are only two hard things in computer science: cache validation and naming things.” Seems like you found a way to work on both! https://skeptics.stackexchange.com/questions/19836/has-phil-karlton-ever-said-there-are-only-two-hard-things-in-computer-science#39178 https://skeptics.stackexchange.com/questions/19836/has-phil-...

timeimp 3y ago
I always have to add the "and off-by-one" at the end. Nothing like reading memory you don't own!
- airstrike 3y ago
  There are actually only two hard problems in computer science: 0) Cache invalidation 1) Naming things 5) Asynchronous callbacks 2) Off-by-one errors 3) Scope creep 6) Bounds checking
  - alternative_a 3y ago
    Let’s be pedantic here and get all religious over the words “Science” and “hard”. Computer “science” has a difficult conceptual problem with caching. The optimal cache, this science tells us, is indistinguishable from a fortune teller who is never wrong (oracle). Fortune telling is a “hard” problem for a science based on reasoning. The best we can do is hedge bets (which is what the science of caching focuses on). This same science also has a difficulty with naming things. Now numbering things is easy and science loves maths and maths love sciences, but science and letters have a more difficult history. Science would approve of “factoryfactoryfactoryImpl” btw ... it’s “a rational scheme of naming”. . Here we see a “science” that is facing actual difficulties. The rest of your list are difficult but not “hard”. The science of these matters is clear and the rest is up to the “scientists” struggling with “scope creep” and “bounds checking” ..
  - Scarblac 3y ago
    There is only one hard problem in software engineering: people.
pmarreck 3y ago
invalidation?
- Hnrobert42 3y ago
  Yes. Stupid speech to text and I didn’t double check. Thanks.

j-pb 3y ago

These things are usually called "persistent" versions of the thing, e.g. persistent Dictionary. Sometimes "immutably persistent" to distinguish it from the "durable" meaning of persistence i.e. written to disk.

btilly 3y ago
It seems odd to me to call a data structure "persistent" when its purpose is to allow you to cheaply keep many similar transitory copies around until you throw them away. The specific application was using dynamic programming to build up a complex data structure. You wind up with many copies of very similar data structures, and doing a deep copy each time is prohibitively expensive.
- ncruces 3y ago
  Still that's what they're called: https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure Precisely because previous versions remain valid (persist) under modification.
  - btilly 3y ago
    There is a key difference between that, and what I created. The difference is that persistent data structures allow you to traverse the history of the data structure to find past versions. By contrast I only allowed you to see the current version, returning a new version of the root any time you made a modification. As a result, the memory associated with the old version could be freed once nothing would want to access it again. And any version that you had could still be manipulated. For the example that I was dealing with, both made sense. On top of that it made it possible to create a hashable version of the data structure that had a good chance (not a guarantee) of matching hashes when you arrived at the same data structure through different histories.
    - ncruces 3y ago
      Well, the difference isn't that great. You wrote: “the memory associated with the old version could be freed once nothing would want to access it again.” So all it really takes is something wanting.