On 20 March 2016 at 21:05, Gabríel Arthúr Pétursson gabriel@system.is wrote:
struct wine_rb_stack {
- struct wine_rb_entry ***entries; size_t count;
- size_t size;
- struct wine_rb_entry **entries[2 * sizeof(void *) * 8];
};
Why do you think this is a good idea?
On Sun, Mar 20, 2016 at 9:50 PM, Henri Verbeet hverbeet@gmail.com wrote:
Why do you think this is a good idea?
This removes the need for custom allocators.
It's particularly helpful in my work to add Vulkan support where I can map Vulkan handles to custom allocators passed in by an application for host memory allocations when creating said handle. Since allocation of host memory by the driver has to go through these custom allocators, if provided, I saw only two options:
1) Add a userdata parameter to rbtree's allocators, or, 2) Remove them since we know there's a small upper bound on the stack size needed.
I opted for the second option due to its simplicity.
Hope this answers your question!
On 20 March 2016 at 23:07, Gabríel Arthúr Pétursson gabriel@system.is wrote:
On Sun, Mar 20, 2016 at 9:50 PM, Henri Verbeet hverbeet@gmail.com wrote:
Why do you think this is a good idea?
This removes the need for custom allocators.
It's particularly helpful in my work to add Vulkan support where I can map Vulkan handles to custom allocators passed in by an application for host memory allocations when creating said handle. Since allocation of host memory by the driver has to go through these custom allocators, if provided, I saw only two options:
- Add a userdata parameter to rbtree's allocators, or,
- Remove them since we know there's a small upper bound on the stack
size needed.
I opted for the second option due to its simplicity.
Hope this answers your question!
Could you give an example of how you're using this, and perhaps a reference to the relevant documentation? Either way, this would make struct wine_rb_tree a lot larger, and I don't think we want that.
Henri Verbeet hverbeet@gmail.com writes:
Could you give an example of how you're using this, and perhaps a reference to the relevant documentation? Either way, this would make struct wine_rb_tree a lot larger, and I don't think we want that.
While we probably don't want that in all cases, having the option of a simpler, allocation-free rbtree would be nice. I suspect there are a number of global lists that could benefit from that.
On 21 March 2016 at 04:50, Alexandre Julliard julliard@winehq.org wrote:
While we probably don't want that in all cases, having the option of a simpler, allocation-free rbtree would be nice. I suspect there are a number of global lists that could benefit from that.
I don't know. I think that outside of D3D it's only used in dbghelp and winemenubuilder, and at least in the winemenubuilder case it might be better to just sort the prog ID list before using it to generate associations. As for the usage in D3D, I think there could potentially be value in having a stack per-thread instead of per-rbtree, but I don't think that would necessarily make things simpler. Having a fixed stack size could certainly be done, but I don't think simply increasing the size of struct wine_rb_tree would make things better for any of the existing cases.
If I were to make an API change, I'd probably split the compare function out of struct wine_rb_functions, replace the allocation functions with functions to manage the rbtree stack, and then provide a default HeapAlloc() or RtlAllocateHeap() based implementation for those.
Henri Verbeet hverbeet@gmail.com writes:
On 21 March 2016 at 04:50, Alexandre Julliard julliard@winehq.org wrote:
While we probably don't want that in all cases, having the option of a simpler, allocation-free rbtree would be nice. I suspect there are a number of global lists that could benefit from that.
I don't know. I think that outside of D3D it's only used in dbghelp and winemenubuilder, and at least in the winemenubuilder case it might be better to just sort the prog ID list before using it to generate associations. As for the usage in D3D, I think there could potentially be value in having a stack per-thread instead of per-rbtree, but I don't think that would necessarily make things simpler. Having a fixed stack size could certainly be done, but I don't think simply increasing the size of struct wine_rb_tree would make things better for any of the existing cases.
Sure, for the existing cases it's fine. My feeling is that there may be more use cases if it was more straightforward to use. I know that a couple of times I considered using an rbtree but didn't, because I felt the potential gain wasn't worth the complexity (not only the extra functions, but also the need to add error handling for allocation failures).
On 21 March 2016 at 11:25, Alexandre Julliard julliard@winehq.org wrote:
Henri Verbeet hverbeet@gmail.com writes:
On 21 March 2016 at 04:50, Alexandre Julliard julliard@winehq.org wrote:
While we probably don't want that in all cases, having the option of a simpler, allocation-free rbtree would be nice. I suspect there are a number of global lists that could benefit from that.
I don't know. I think that outside of D3D it's only used in dbghelp and winemenubuilder, and at least in the winemenubuilder case it might be better to just sort the prog ID list before using it to generate associations. As for the usage in D3D, I think there could potentially be value in having a stack per-thread instead of per-rbtree, but I don't think that would necessarily make things simpler. Having a fixed stack size could certainly be done, but I don't think simply increasing the size of struct wine_rb_tree would make things better for any of the existing cases.
Sure, for the existing cases it's fine. My feeling is that there may be more use cases if it was more straightforward to use. I know that a couple of times I considered using an rbtree but didn't, because I felt the potential gain wasn't worth the complexity (not only the extra functions, but also the need to add error handling for allocation failures).
Allocating the maximum stack size on initialisation in exchange for never having allocation failures could be worth it, yeah. Note that wine_rb_put() can also fail when trying to insert duplicate values though. I suppose we could change that to either replace the existing entry or to fail silently.
On 03/21/16 12:38, Henri Verbeet wrote:
On 21 March 2016 at 11:25, Alexandre Julliard julliard@winehq.org wrote:
Henri Verbeet hverbeet@gmail.com writes:
On 21 March 2016 at 04:50, Alexandre Julliard julliard@winehq.org wrote:
While we probably don't want that in all cases, having the option of a simpler, allocation-free rbtree would be nice. I suspect there are a number of global lists that could benefit from that.
I don't know. I think that outside of D3D it's only used in dbghelp and winemenubuilder, and at least in the winemenubuilder case it might be better to just sort the prog ID list before using it to generate associations. As for the usage in D3D, I think there could potentially be value in having a stack per-thread instead of per-rbtree, but I don't think that would necessarily make things simpler. Having a fixed stack size could certainly be done, but I don't think simply increasing the size of struct wine_rb_tree would make things better for any of the existing cases.
Sure, for the existing cases it's fine. My feeling is that there may be more use cases if it was more straightforward to use. I know that a couple of times I considered using an rbtree but didn't, because I felt the potential gain wasn't worth the complexity (not only the extra functions, but also the need to add error handling for allocation failures).
Allocating the maximum stack size on initialisation in exchange for never having allocation failures could be worth it, yeah. Note that wine_rb_put() can also fail when trying to insert duplicate values though. I suppose we could change that to either replace the existing entry or to fail silently.
There are more options to consider. A few that come to mind are:
- If constant stack size is enough, we could simply have it as a regular C array in functions that need the stack. The array doesn't seem to big to worry about stack usage and we'd have wine_rb_tree even smaller this way. It's also faster than allocating stack on the heap.
- Since depth of the stack doesn't seem too bad, we could easily use recursion for the implementation. Doing it in a smart way would avoid the need for the stack at all (at cost of higher C stack usage).
- If we stored parent in each node, I think we could get away without having the stack at all. It would have its drawback of increasing memory usage by O(n) and possibly fixup time would be O(log n ^2) instead of O(log n) (although I'm pretty sure we could make it O(log n) in practice). The big potential gain from this is that we could easily implement linear-time traversal with this, so we'd potentially have more use cases. Lack of iteration capabilities in current implementation is the main reason it can't be used in places like vbscript for storing object properties.
Cheers, Jacek
On 03/21/16 12:54, Jacek Caban wrote:
and possibly fixup time would be O(log n ^2) instead of O(log n) (although I'm pretty sure we could make it O(log n) in practice).
Scratch that, it wouldn't affect fixup time at all.
Cheers, Jacek
On 21 March 2016 at 12:54, Jacek Caban jacek@codeweavers.com wrote:
- If constant stack size is enough, we could simply have it as a regular
C array in functions that need the stack. The array doesn't seem to big to worry about stack usage and we'd have wine_rb_tree even smaller this way. It's also faster than allocating stack on the heap.
I don't think allocation speed is really an issue here.
- Since depth of the stack doesn't seem too bad, we could easily use
recursion for the implementation. Doing it in a smart way would avoid the need for the stack at all (at cost of higher C stack usage).
It's certainly possible to do a recursive implementation. I tend to find explicit stacks easier to follow though.
- If we stored parent in each node, I think we could get away without
having the stack at all. It would have its drawback of increasing memory usage by O(n) and possibly fixup time would be O(log n ^2) instead of O(log n) (although I'm pretty sure we could make it O(log n) in practice). The big potential gain from this is that we could easily implement linear-time traversal with this, so we'd potentially have more use cases. Lack of iteration capabilities in current implementation is the main reason it can't be used in places like vbscript for storing object properties.
If you don't mind requiring aligned pointers, you could merge the parent pointer with the flags field. What is the issue with wine_rb_for_each_entry() though?
On 03/21/16 14:04, Henri Verbeet wrote:
On 21 March 2016 at 12:54, Jacek Caban jacek@codeweavers.com wrote:
- If constant stack size is enough, we could simply have it as a regular
C array in functions that need the stack. The array doesn't seem to big to worry about stack usage and we'd have wine_rb_tree even smaller this way. It's also faster than allocating stack on the heap.
I don't think allocation speed is really an issue here.
That's just an additional advantage, not the main point. If that's your only concern, should I understand that you like the idea?
- Since depth of the stack doesn't seem too bad, we could easily use
recursion for the implementation. Doing it in a smart way would avoid the need for the stack at all (at cost of higher C stack usage).
It's certainly possible to do a recursive implementation. I tend to find explicit stacks easier to follow though.
- If we stored parent in each node, I think we could get away without
having the stack at all. It would have its drawback of increasing memory usage by O(n) and possibly fixup time would be O(log n ^2) instead of O(log n) (although I'm pretty sure we could make it O(log n) in practice). The big potential gain from this is that we could easily implement linear-time traversal with this, so we'd potentially have more use cases. Lack of iteration capabilities in current implementation is the main reason it can't be used in places like vbscript for storing object properties.
If you don't mind requiring aligned pointers, you could merge the parent pointer with the flags field.
Yes, that's true even without parent pointers (we could merge them with left/right pointers). I personally find such requirement something that's better avoided, but if concerns about memory usage would prevent implementing things this way, I think it would be worth it the requirement.
What is the issue with wine_rb_for_each_entry() though?
wine_rb_for_each_entry can only walk the whole tree, you can't just do something like next_node() with it. Even in cases where it's enough, I find a loop cleaner than having to create new callback function. We could even have something like LIST_FOR_EACH for rb trees.
I tend to like that last option the most with preference like 3 > 2 > 1 > any solution storing stack in the tree. What's your opinion?
Jacek
On 21 March 2016 at 14:53, Jacek Caban jacek@codeweavers.com wrote:
On 03/21/16 14:04, Henri Verbeet wrote:
On 21 March 2016 at 12:54, Jacek Caban jacek@codeweavers.com wrote:
- If constant stack size is enough, we could simply have it as a regular
C array in functions that need the stack. The array doesn't seem to big to worry about stack usage and we'd have wine_rb_tree even smaller this way. It's also faster than allocating stack on the heap.
I don't think allocation speed is really an issue here.
That's just an additional advantage, not the main point. If that's your only concern, should I understand that you like the idea?
"Like" is perhaps stronger than what I'd use, but I'm not necessarily opposed to it.
Yes, that's true even without parent pointers (we could merge them with left/right pointers). I personally find such requirement something that's better avoided, but if concerns about memory usage would prevent implementing things this way, I think it would be worth it the requirement.
Yeah.
What is the issue with wine_rb_for_each_entry() though?
wine_rb_for_each_entry can only walk the whole tree, you can't just do something like next_node() with it. Even in cases where it's enough, I find a loop cleaner than having to create new callback function. We could even have something like LIST_FOR_EACH for rb trees.
Right. Perhaps it's mostly lack of imagination, but I can't think of a lot of cases where you'd use a hypothetical wine_rb_next() / wine_rb_prev() instead of applying an operation on the entire tree, and wouldn't already have the entries be part of some sort of existing list. But yeah, parent pointers would make that easier.
I tend to like that last option the most with preference like 3 > 2 > 1 > any solution storing stack in the tree. What's your opinion?
I think parent pointers would be fine. I didn't use those originally because it's an extra field and I didn't really need them, but if there's a good use-case for them that's probably worth it.
On 21 March 2016 at 15:16, Henri Verbeet hverbeet@gmail.com wrote:
I think parent pointers would be fine. I didn't use those originally because it's an extra field and I didn't really need them, but if
Actually, to put that in perspective a bit, the rbtree was originally meant to be something internal to wined3d, but Alexandre figured it could be more generally usable.
-
Alexandre Julliard -
Gabríel Arthúr Pétursson -
Henri Verbeet -
Jacek Caban