5 ms·

Too often that I find the C extension projects introduced here on HN would omit examples for dynamically allocated objects. In the binary tree example, apparent

Too often that I find the C extension projects introduced here on HN would omit examples for dynamically allocated objects. In the binary tree example, apparently I can't just memcpy an existing tree to a malloc'd tree because the nodes would point to the ones on the old tree. I was halfway writing a copy function that recursively traverses the source tree, void copy(BinaryTree *dest, const BinaryTree *src) { match(*src) { of(Leaf, x) { *dest = TREE(Leaf(x)); } } } then realised that this still points to a leaf on the stack. Need a way to replace all the pointers to be relative to the destination tree...

lasagnaphil 6y ago
Isn’t that a problem even in managed, garbaged-collected languages? For most (procedural) languages it’s a bit involved if you want to deep-copy heap-allocated objects. If you don’t want the overhead of re-creating the tree from scratch, you can use indices instead of pointers and store the nodes in a heap-allocated contiguous array, and then when you want to create a deep copy of the tree you can just memcpy the whole array in one go.
- dataflow 6y ago
  I'm guessing they're coming from C++ or similar where the copy constructors already take care of making a deep copy.
  - lasagnaphil 6y ago
    Still, inside that copy constructor you're going to write the exact boilerplate code for recursively copying each node, so the complexity of code won't change that much. Also, you're going to call quite a lot of malloc/free, which could be a potential performance hit if you're creating/destroying large trees a lot, as well as fragmenting your memory if you're not careful. Personally I have a much easier time dealing with tree/graph data structures using indices, regardless of the language I'm using. Using indices as handles in general are just so much easier than using pointers in terms of memory management, and generally performs much better in terms of cache coherency. Indices are also easier to serialize/deserialize, and sometimes it just "makes sense" (for example, if you're developing a physics simulation, representing objects as indices are natural because you're going to use those index values inside various math equations.) The downside might be that if you're creating and destroying nodes in a tree continuously. then you have to be careful about reusing indices. There's a pattern in gamedev (generational indices) that solve the issue (basically, in addition to an index you also store a counter value with it, and you increment the counter everytime you allocate a new node in the same spot of the array. It's a bit more bookkeeping, but there's lots of code examples for it. It's kind of a well-known trick inside gamedev (and recently in the Rust community, in order to bypass borrow checker issues). A few pointers: - https://floooh.github.io/2018/06/17/handles-vs-pointers.html https://floooh.github.io/2018/06/17/handles-vs-pointers.html - https://kyren.github.io/2018/09/14/rustconf-talk.html https://kyren.github.io/2018/09/14/rustconf-talk.html - https://news.ycombinator.com/item?id=17995634 https://news.ycombinator.com/item?id=17995634 (steveklabnik explaining how generational indices work with code).
boomlinde 6y ago
The allocation strategy used is only a tangential problem. The purpose of the example is to demonstrate the functionality of the library in brief, not to walk the reader through problems that C programmers face in general. I would suggest recursively walking through the original tree, creating an equivalent tree in the process instead of copying the original elements.
- syockit 6y ago
  Yeah, I suppose. /* get size required for malloc */ size_t getsize(const BinaryTree *tree) { size_t acc = sizeof(*tree); match(*tree) { of(Leaf, x) { return acc; } of(Node, lhs, x, rhs) { return getsize(*lhs) + acc + getsize(*rhs); } } } BinaryTree* copy(BinaryTree *dest, const BinaryTree *src) { dest->tag = src->tag; match(*src) { of(Leaf, x) { *dest = Leaf(*x); } of(Node, lx, x, rx) { match(*dest) { of(Node, ly, y, ry) { *ly = dest + 1; *ry = copy(*ly, *lx); *y = *x; copy(*ry, *rx); } otherwise {} } } } return dest + 1; } Kind of hackish, but I guess it works.
  - klodolph 6y ago
    Hackish????

lasagnaphil 6y ago

Isn’t that a problem even in managed, garbaged-collected languages? For most (procedural) languages it’s a bit involved if you want to deep-copy heap-allocated objects. If you don’t want the overhead of re-creating the tree from scratch, you can use indices instead of pointers and store the nodes in a heap-allocated contiguous array, and then when you want to create a deep copy of the tree you can just memcpy the whole array in one go.

dataflow 6y ago
I'm guessing they're coming from C++ or similar where the copy constructors already take care of making a deep copy.
- lasagnaphil 6y ago
  Still, inside that copy constructor you're going to write the exact boilerplate code for recursively copying each node, so the complexity of code won't change that much. Also, you're going to call quite a lot of malloc/free, which could be a potential performance hit if you're creating/destroying large trees a lot, as well as fragmenting your memory if you're not careful. Personally I have a much easier time dealing with tree/graph data structures using indices, regardless of the language I'm using. Using indices as handles in general are just so much easier than using pointers in terms of memory management, and generally performs much better in terms of cache coherency. Indices are also easier to serialize/deserialize, and sometimes it just "makes sense" (for example, if you're developing a physics simulation, representing objects as indices are natural because you're going to use those index values inside various math equations.) The downside might be that if you're creating and destroying nodes in a tree continuously. then you have to be careful about reusing indices. There's a pattern in gamedev (generational indices) that solve the issue (basically, in addition to an index you also store a counter value with it, and you increment the counter everytime you allocate a new node in the same spot of the array. It's a bit more bookkeeping, but there's lots of code examples for it. It's kind of a well-known trick inside gamedev (and recently in the Rust community, in order to bypass borrow checker issues). A few pointers: - https://floooh.github.io/2018/06/17/handles-vs-pointers.html https://floooh.github.io/2018/06/17/handles-vs-pointers.html - https://kyren.github.io/2018/09/14/rustconf-talk.html https://kyren.github.io/2018/09/14/rustconf-talk.html - https://news.ycombinator.com/item?id=17995634 https://news.ycombinator.com/item?id=17995634 (steveklabnik explaining how generational indices work with code).

boomlinde 6y ago

The allocation strategy used is only a tangential problem. The purpose of the example is to demonstrate the functionality of the library in brief, not to walk the reader through problems that C programmers face in general. I would suggest recursively walking through the original tree, creating an equivalent tree in the process instead of copying the original elements.

syockit 6y ago
Yeah, I suppose. /* get size required for malloc */ size_t getsize(const BinaryTree *tree) { size_t acc = sizeof(*tree); match(*tree) { of(Leaf, x) { return acc; } of(Node, lhs, x, rhs) { return getsize(*lhs) + acc + getsize(*rhs); } } } BinaryTree* copy(BinaryTree *dest, const BinaryTree *src) { dest->tag = src->tag; match(*src) { of(Leaf, x) { *dest = Leaf(*x); } of(Node, lx, x, rx) { match(*dest) { of(Node, ly, y, ry) { *ly = dest + 1; *ry = copy(*ly, *lx); *y = *x; copy(*ry, *rx); } otherwise {} } } } return dest + 1; } Kind of hackish, but I guess it works.
- klodolph 6y ago
  Hackish????