GNOME Bugzilla – Bug 602255
Persistent GTree
Last modified: 2018-05-24 12:01:05 UTC
Created attachment 148001 [details] [review] 1st patch Hello, I've implemented a persistent version of a GTree. I sent an email to the gtk-devel list about this recently [1], which describes what a persistent binary search tree is, and why I wanted to this. I have a git repository with the patches in it [2] and I will also attach the necessary patches, created with git-format-patch, to this request. There is an additional feature in the middle of this, which is to allow searching for the nearest neighbour of a key in a GTree, when the searched key is not present in the tree. This is in the second patch of the series. Lastly, I have written a report [3] detailing my implementation decisions, and showing benchmarks comparing the persistent GTree to the current upstream implementation. The report shows the performance of the persistent trees to be roughly equal to the upstream implementation (a bit faster sometimes, a bit slower sometimes, but by only an epsilon constant factor). I would definitely like to see this added to upstream, so if you have any issues with the code, or with the interface, let me know and I will address them. I will include any additional changes as further patches to the attached patch-set. Thanks! [1] http://www.mail-archive.com/gtk-devel-list@gnome.org/msg10799.html [2] http://git.icculus.org/?p=dana/cg-glib.git [3] http://cg.scs.carleton.ca/~dana/pbst/
Created attachment 148002 [details] [review] 2nd patch
Created attachment 148003 [details] [review] 3rd patch
Created attachment 148004 [details] [review] 4th patch
Created attachment 148005 [details] [review] 5th patch
Created attachment 148006 [details] [review] 6th patch
I would like to point out an additional observation. The current upstream GTree implementation is a pointer-based structure, as is the persistent GTree implemented in these patches. And both are near-optimal in their space and performance for a pointer-based structure. It may be possible in the future to improve the performance of the current GTree some by making it a cache-oblivious data structure, and thus no longer pointer based. Persistence requires that the structure remain pointer-based in order to work efficiently, and so if this is a serious possibility/requirement, it may be desirable to keep a separate persistent tree implementation. I'd of course be happy to provide patches to adjust it to that model if that was the case, there's a lot of "if"s involved though, so someone would some idea of/authority on where GTree should be going in the future needs to say something here.
I recently moved my git repositories to a new home. The same git tree now resides at http://git.openbox.org/?p=dana/cg-glib.git Thanks.
-- GitLab Migration Automatic Message -- This bug has been migrated to GNOME's GitLab instance and has been closed from further activity. You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/glib/issues/248.