COW radix tree

[miekg]

To be really (really) useful a copy-on-write variant of radix would be nice. It will probably need a parental pointer in each node and ofcourse code that deals with the copy-on-write part.

[sauerbraten]

Mhm, I've never done COW, and don't quite see the sense. Would a COW radix mean that 2 callers read from the same tree, and if caller A makes changes to a node, a copy of that node is generated which is only visible to A? Or a copy of the whole tree? Why would I want changes to be only visible to one caller?

[miekg]

[ Quoting <reply+i-5657470-80779761e> in "Re: [radix] COW radix tree (#5)..." ]

Mhm, I've never done COW, and don't quite see the sense. Would a COW radix mean that 2 callers read from the same tree, and if caller A makes changes to a node, a copy of that node is generated which is only visible to A? Or a copy of the whole tree? Why would I want changes to be only visible to one caller?

COW is not about changes being visible to one caller, its about changes being
atomic for the readers. So both readers and writers can do what they want
and the tree (they see) will always be in a consistent state.

COW and tree means path copying as explained here:
http://hackerboss.com/copy-on-write-101-part-1-what-is-it/

... and the followup posts.

Regards,

Miek Gieben                                                   http://miek.nl

[sauerbraten]

Ok I got the point of COW for radix now. I believe we could get away without a parent pointer if we really want to implement it, though it would be a little bit 'dirty':
We could write a function GetPath(key string) (*Radix, []byte) {} which is similar to Find(), but adds the first char of the child it walks down into ( = the byte that is used in the children map) to a []byte which is returned with the *Radix, so we do not have to walk up the nodes when creating copies. Would that work?

Also, I'm thinking about writing a Find() function which uses a loop instead of recursion, so that appending bytes to the []byte would be easier. (The recursive way would need to pass the slice along on every call, wouldn't it?). Actually all the methods (Find(), Remove(), and Insert()) could be written using a loop. Is there any advantage in using recursion over loops?

[sauerbraten]

Couldn't find any usecase in which COW has a benefit. Closing this issue.