5 ms·

You are probably thinking of ARC which is automatic (not "atomic") reference counting a la Bacon/Dingle [1] via Nim's --gc:arc/orc. Because some people do not

by cb321 6y ago

You are probably thinking of ARC which is automatic (not "atomic") reference counting a la Bacon/Dingle [1] via Nim's --gc:arc/orc. Because some people do not consider any "reference counting" to be "garbage collection, I think "automatic memory management" a more clear term. Regardless, you can turn off all automatic memory mgmt with --gc:none, though the stdlib won't cooperate much. --gc:arc/orc is fairly practical, though still not quite as bug free as, say, --gc:markAndSweep. Nim gives you many options for many things. Ref counts have a reputation for being slower than mark/sweep/generational/etc AMMs, but (with a lot of compiler assistance/optimizations) they seem at least as fast (and maybe faster) in practice, at least with Nim which usually performs like C/Rust/etc. [1] https://researcher.watson.ibm.com/researcher/files/us-bacon/Dingle07Ownership.pdf https://researcher.watson.ibm.com/researcher/files/us-bacon/...

59nadir 6y ago
How does Nim deal with passing allocators to things? Does the standard library have a story for this?
- cb321 6y ago
  Someone just asked almost this question in the Nim Forum [1] (coincidentally, unless that was you!). So, you may want to follow that conversation. (EDIT: It may be more global than you are used to in Zig (or than you need/want), but might also be "good enough", depending.) [1] https://forum.nim-lang.org/t/7588 https://forum.nim-lang.org/t/7588
  - 59nadir 6y ago
    Thanks for the link. The asker wasn't me. I suppose I would just create my own types/functions that take actual allocators if I were to use Nim. It's more work than you'd like, but the alternative isn't really good enough.
    - cb321 6y ago
      I do not know enough Zig to be sure, but an oft overlooked wrinkle in custom allocators is the width of pointer types aka labels for the allocated regions. Focus is usually on "packing efficiency" or MT-sharing and such of the allocation arenas themselves, not labels of allocated items. Perhaps you could speak to this? For example, a binary tree with <65536 nodes could use 2 byte pointers and in-node space overhead might be just 4B and if you had, say, 4B floats as key-values this might be "only" 100% space overhead with 8B per node total instead of C++ STL-like 8B x 3 (parent pointers) + other extra junk overhead. (IIRC, I measured it once as 80 bytes per node in the default `std::set` impl...). In Nim, one could probably address this kind of situation with distinct types: type nodePtr = distinct uint16 and overloading `[]` and so on in terms of this new `nodePtr` type. Since virtual memory dereference needs no extra "deref context", global variables/closures/local context (like an ever present proc parameter) may be needed to fully convert a narrow pointer to a VM pointer (or to otherwise access data). I think that this is all do-able in Nim, the language, but the stdlib has no direct conventions. You might be able to keep using the rest of the stdlib by swapping out the impl of newSeq or newString to take a named parameter defaulting to some global arena, but call site-specializable to whatever you want and then replacing the `string` and `seq` types which propagate this not quite hidden optional parameter, getting the nice usability/brevity of a global arena with the nice tunability of specialized allocators. A macro pragma might even make propagating the allocator handle to called procs that also allocate semi-automatic (but someone would need to get PRs in to annotate all needed stdlib procs...). I am unaware of any Nim project which has done this yet. So, there could be compiler/run-time bugs in the way or other blockades. And it may not be possible to have narrow pointer types as with my binary tree example (but this may also not be possible with Zig's conventions). This is all really just a little color on your probably correct conclusion (and a question about how flexible Zig's pointer types can be in its stdlib convention). EDIT: Oh, and though that Forum asker was not you, you may get better answers than from just me here by making an account there and asking on the Nim Forum.
randomswede 6y ago
To me, the main issue with ref-counting isn't "speed", it is "correctness" or "completeness". Ref-counting cannot cope with cycles in data structures. This can be worked around by contorting your code to work around the issue, but is not what I would call an ideal situation (it creates edge cases that more natural code would be able to cope with), simply to work around limitations in the GC (I will claim it's GC, just not as good as other reachability checkers).
- cb321 6y ago
  Well, I was replying to AMM optionality, not completeness. Nim has ORC to break cycles - ref ct + cycle checker. I believe Python grew the same thing eventually from similar refcount beginnings. So, completeness worries need not push you away from Nim. As mentioned, there are many options. These techniques still seem to be called "adjusted/qualified ref counting" rather than "garbage collection". So, I believe terminological problems have muddied the waters yet again. Or else my own incomplete description did { to the extent that differs at all. :-) }
  - randomswede 6y ago
    Yeah, once you start talking about "not pure ref counting" (that is, ad din cycle checkers and what have you), the cost of ref-counting goes up dramatically. I was trying to differentiate between "garbage collection" (the memory management family of techniques) and "specific species of algorithms for GC" (where I would class "pure reference counting" as one, and various augmentations of ref-counting as several more, as well as stop-and-copy, o the easier side).
    - cb321 6y ago
      Costs can go up, but do not always. Nim has some `acyclic` pragmas to help. Answers to almost all performance questions include a "depends", but now we are back on "speed" not completeness. :-) Anyway, you can probably just use `nim c --gc:markAndSweep` to worry less.
      - 6y ago

by cb321 6y ago

59nadir 6y ago

How does Nim deal with passing allocators to things? Does the standard library have a story for this?

cb321 6y ago
Someone just asked almost this question in the Nim Forum [1] (coincidentally, unless that was you!). So, you may want to follow that conversation. (EDIT: It may be more global than you are used to in Zig (or than you need/want), but might also be "good enough", depending.) [1] https://forum.nim-lang.org/t/7588 https://forum.nim-lang.org/t/7588
- 59nadir 6y ago
  Thanks for the link. The asker wasn't me. I suppose I would just create my own types/functions that take actual allocators if I were to use Nim. It's more work than you'd like, but the alternative isn't really good enough.
  - cb321 6y ago
    I do not know enough Zig to be sure, but an oft overlooked wrinkle in custom allocators is the width of pointer types aka labels for the allocated regions. Focus is usually on "packing efficiency" or MT-sharing and such of the allocation arenas themselves, not labels of allocated items. Perhaps you could speak to this? For example, a binary tree with <65536 nodes could use 2 byte pointers and in-node space overhead might be just 4B and if you had, say, 4B floats as key-values this might be "only" 100% space overhead with 8B per node total instead of C++ STL-like 8B x 3 (parent pointers) + other extra junk overhead. (IIRC, I measured it once as 80 bytes per node in the default `std::set` impl...). In Nim, one could probably address this kind of situation with distinct types: type nodePtr = distinct uint16 and overloading `[]` and so on in terms of this new `nodePtr` type. Since virtual memory dereference needs no extra "deref context", global variables/closures/local context (like an ever present proc parameter) may be needed to fully convert a narrow pointer to a VM pointer (or to otherwise access data). I think that this is all do-able in Nim, the language, but the stdlib has no direct conventions. You might be able to keep using the rest of the stdlib by swapping out the impl of newSeq or newString to take a named parameter defaulting to some global arena, but call site-specializable to whatever you want and then replacing the `string` and `seq` types which propagate this not quite hidden optional parameter, getting the nice usability/brevity of a global arena with the nice tunability of specialized allocators. A macro pragma might even make propagating the allocator handle to called procs that also allocate semi-automatic (but someone would need to get PRs in to annotate all needed stdlib procs...). I am unaware of any Nim project which has done this yet. So, there could be compiler/run-time bugs in the way or other blockades. And it may not be possible to have narrow pointer types as with my binary tree example (but this may also not be possible with Zig's conventions). This is all really just a little color on your probably correct conclusion (and a question about how flexible Zig's pointer types can be in its stdlib convention). EDIT: Oh, and though that Forum asker was not you, you may get better answers than from just me here by making an account there and asking on the Nim Forum.

randomswede 6y ago

To me, the main issue with ref-counting isn't "speed", it is "correctness" or "completeness". Ref-counting cannot cope with cycles in data structures. This can be worked around by contorting your code to work around the issue, but is not what I would call an ideal situation (it creates edge cases that more natural code would be able to cope with), simply to work around limitations in the GC (I will claim it's GC, just not as good as other reachability checkers).

cb321 6y ago
Well, I was replying to AMM optionality, not completeness. Nim has ORC to break cycles - ref ct + cycle checker. I believe Python grew the same thing eventually from similar refcount beginnings. So, completeness worries need not push you away from Nim. As mentioned, there are many options. These techniques still seem to be called "adjusted/qualified ref counting" rather than "garbage collection". So, I believe terminological problems have muddied the waters yet again. Or else my own incomplete description did { to the extent that differs at all. :-) }
- randomswede 6y ago
  Yeah, once you start talking about "not pure ref counting" (that is, ad din cycle checkers and what have you), the cost of ref-counting goes up dramatically. I was trying to differentiate between "garbage collection" (the memory management family of techniques) and "specific species of algorithms for GC" (where I would class "pure reference counting" as one, and various augmentations of ref-counting as several more, as well as stop-and-copy, o the easier side).
  - cb321 6y ago
    Costs can go up, but do not always. Nim has some `acyclic` pragmas to help. Answers to almost all performance questions include a "depends", but now we are back on "speed" not completeness. :-) Anyway, you can probably just use `nim c --gc:markAndSweep` to worry less.
    - 6y ago