[RFC] a plan for piles
13 views
Skip to first unread message
Nick Black
Nov 21, 2020, 9:34:42 PM11/21/20
to team notcurses
I am introducing a new concept to Notcurses, that of a **pile**.
A pile is a collection of ncplanes, with two orderings:
* a partial ordering of ownership, the bindtree
* a total ordering of position, the z-axis
Both of these backbone structures already exist in a
`struct notcurses`, with their state encoded into
`struct ncplane`. The only difference is that these orderings
become a forest rather than a tree (and degenerate tree).
If it's not obvious, this is being done in the name of parallelism. Mutating
any plane during a rendering operation is not currently allowed. With this
change in place, mutating a pile while another is being rendered is totally
safe, allowing for double (or n-ary) buffering relative to render+raster,
as opposed to merely rasterization (as can currently be theoretically
accomplished using notcurses_render_to_buffer(), though we never made
notcurses_rasterize() public, so I'm unsure how that was supposed to work).
Action items follow, with reasoning; RFC:
0) new internal type ncpile will be added
We pretty much have to have this struct, which I'd originally
hoped to forgo. Why? Well, we need both a zaxis (for rendering)
and a bindtree (for...binding). While most of the space for
these data structures is inlined into the relevant ncplane
structs, we need a handle on the zaxis top (for starting the
render of a pile in O(1)) at minimum. I don't like the idea of
making the user externally track the top of a pile's zaxis (as
they would need do if we simply changed notcurses_render() to
take an ncplane), nor do I like the idea of rendering requiring
an O(N) walk up the zaxis. Rendering from an ncplane handle
requires only the O(1) pile lookup now, so there's no need for
the user to track the pile.
It is possible that we will keep the ncpile concept internal,
though I don't think so -- a user calling ncplane_render() on an
ncplane presumably expects to start rendering from that ncplane;
a user calling ncplane_move_top() on two ncplanes A+B presumably
expects an action on A+B, not A+B's pile. I'm unsure. It's a
matter of taste, not of technology. So these will likely be
renamed with ncpile, but the actual type will never be
referenced externall.
1) ncplane will no longer point directly to struct notcurses
2) ncplane will point to ncpile
3) ncpile will point to struct notcurses
This way, we can reach both pile and containing context in two
O(1) pointer derefs, requiring only one additional pointer per
pile for this tracking. Looking up a notcurses struct from an
ncpile doesn't seem to happen frequently enough that the extra
pointer deref would have much effect on performance.
4) A new flag will be added to ncplane_options, NCPLANE_OPTION_NEWPILE,
creating the new ncplane on a new ncpile.
This allows the cleanest creation of a pile, when it's known
that a new plane is intended to start one. Extracting a plane
from an existing pile is going to have some overhead, as we'll
see below.
5) An ncplane reparented to itself becomes the root plane of a new
pile, unless it is already a root plane, in which case the
reparenting is a no-op. Bound planes and siblings do not join it
in the new pile. The new zaxis contains of one member.
This action is currently a no-op in all cases. Since a plane
parented to itself is a root plane, this makes total sense as an
expansion of the funtion. Creation of and extraction from zaxes
is O(1).
6) A new function, ncplane_make_sibling(), will be added.
This allows an ncplane to be made a sibling of another.
ncplane_reparent(ncplane_parent(A)) doesn't work if A is a root
plane (sadly), else this would be mere semantic sugar. This
function is being added to cover the case where we want to make
a plane part of the root set of a pile. I imagine this will be a
very rare event, and hesitate to add this function, but it
doesn't make anything more complex -- it's just something of a
wart.
An alternative would be to have root planes return an ncpile as
their parent, to which one could reparent a plane. This has
several downsides: it exposes ncpile, it requires
ncplane_parent() to return either an ncplane or an ncpile, and
it requires ncplane_reparent() to accept either an ncplane or an
ncpile. I feel the approach of ncplane_makesibling() is less an
overall wart.
A second alternative would be to say "fuck it" and not introduce
this function at all. That's such a hit to conceptual simplicity
that I can't countenance it. But maybe I'm missing something...?
Note that a sibling is also created via ncplane_dup().
7) A new function, ncplane_reparent_family(), will be added. This
function works the same way as ncplane_reparent(), except that
it brings along any bound planes.
This is an extension of what already exists after implementing
(5), since the current ncplane_reparent() does not bring along
bound planes (they are rebound to the plane's original parent).
Note that extracting child planes, if they exist, requires a
traversal of the originating zaxis having both O(N) time and
O(N) state--a semi-expensive operation. Piles are ideally
created at ncplane_create() time, and operated on from there.
When reparenting a family within the same pile, there's no need
for these O(N) operations, as the zaxis is not changed.
This is entirely orthogonal to the overall goals of this change,
and who knows, maybe we won't do it.
8) Reparenting an ncplane to an ncplane within another pile places
it immediately above the new parent on the zaxis. Reparenting an
ncplane as a family sees the same behavior, with all moved
children placed atop the reparented plane, retaining their
z-order from the source pile.
There's no logic to where we place the reparented plane within
the new pile's zaxis, so we pick a place -- above the new
parent. The most reasonable alternatives would be either the top
or bottom of the new zaxis. There's no real reason to pick any
of them -- it's an O(1) splice no matter what -- and this seems
most natural.
Just as they do now, bound planes are reparented to the parent
of the reparented plane. If the reparented plane is a root
plane, any bound planes now become root planes.
9) When no references exist to an ncpile, it is destroyed.
This is one reason to keep the ncpile struct hidden -- we know
there are no references outstanding once we detach the last
ncplane. This doesn't require reference counting or anything
like that; we just kill the pile when a plane which is all of a
root, childless, and siblingless is detached.
10) notcurses_render() is loosely deprecated, and operates on the
standard plane's pile.
We will deemphasize notcurses_render(), but there's no immediate
need to get rid of it.
11) ncpile_render_buffer() will be added, taking as its argument an
ncplane, and operating on its pile.
Pretty self-explanatory. I prefer this to ncplane_render_buffer() to
emphasize that we start rendering at the pile's top plane, not at the
provided plane. ncpile_render_buffer() called on any plane from
the standard pile is equivalent to notcurses_render_to_buffer().
12) It is an error to concurrently rasterize rendered buffers,
including rasterizing one while calling notcurses_render()
(which implicitly rasterizes).
I should hope that the reasoning for this is obvious. I list it
primarily to emphasize that rasterizing buffers in a different
order from how they were rendered is perfectly legal, since the
rasterization optimizations based on the currently-rendered
state are not relevant to the process of rendering.
13) notcurses_stop will continue to clean up all state.
No need to manually ensure all ncplanes are destroyed;
notcurses_stop() continues to handle this.
14) It is legal to concurrently mutate distinct piles in any way
one might dream.
The entire point of this exercise. This mainly just means we
don't want to have any concurrently-accessed global list of
ncpiles, nor any data structure that contains planes from
multiple piles. I think we need to have the former to ensure
proper notcurses_stop() cleanup; that's fine, we'll just throw a
lock around it (mutating this list will be a rare operation).
This list will take the form of a doubly-linked list to ensure
O(1) splicing.
This seems entirely backwards-compatible with the old school
(save that ncplane_reparent() now has an action for what was
previously a no-op (but silly) case). I'm willing to break
people who were relying on this no-op (a survey of known
Notcurses projects does not suggest that anyone is). It adds
very little overhead:
state: three 64-bit pointers per pile
time: only O(N) operation is extracting the planes from a pile's
zaxis when calling ncplane_reparent_family()
yet opens up a bold new world of parallelism and flexibilty, and
doesn't complicate the way for #1109 (at which time we'll have a
fully Copernican universe).
https://www.youtube.com/watch?v=RgtNuhOH2q8
--
nick black -=- https://www.nick-black.com
to make an apple pie from scratch,
you need first invent a universe.
A pile is a collection of ncplanes, with two orderings:
* a partial ordering of ownership, the bindtree
* a total ordering of position, the z-axis
Both of these backbone structures already exist in a
`struct notcurses`, with their state encoded into
`struct ncplane`. The only difference is that these orderings
become a forest rather than a tree (and degenerate tree).
If it's not obvious, this is being done in the name of parallelism. Mutating
any plane during a rendering operation is not currently allowed. With this
change in place, mutating a pile while another is being rendered is totally
safe, allowing for double (or n-ary) buffering relative to render+raster,
as opposed to merely rasterization (as can currently be theoretically
accomplished using notcurses_render_to_buffer(), though we never made
notcurses_rasterize() public, so I'm unsure how that was supposed to work).
Action items follow, with reasoning; RFC:
0) new internal type ncpile will be added
We pretty much have to have this struct, which I'd originally
hoped to forgo. Why? Well, we need both a zaxis (for rendering)
and a bindtree (for...binding). While most of the space for
these data structures is inlined into the relevant ncplane
structs, we need a handle on the zaxis top (for starting the
render of a pile in O(1)) at minimum. I don't like the idea of
making the user externally track the top of a pile's zaxis (as
they would need do if we simply changed notcurses_render() to
take an ncplane), nor do I like the idea of rendering requiring
an O(N) walk up the zaxis. Rendering from an ncplane handle
requires only the O(1) pile lookup now, so there's no need for
the user to track the pile.
It is possible that we will keep the ncpile concept internal,
though I don't think so -- a user calling ncplane_render() on an
ncplane presumably expects to start rendering from that ncplane;
a user calling ncplane_move_top() on two ncplanes A+B presumably
expects an action on A+B, not A+B's pile. I'm unsure. It's a
matter of taste, not of technology. So these will likely be
renamed with ncpile, but the actual type will never be
referenced externall.
1) ncplane will no longer point directly to struct notcurses
2) ncplane will point to ncpile
3) ncpile will point to struct notcurses
This way, we can reach both pile and containing context in two
O(1) pointer derefs, requiring only one additional pointer per
pile for this tracking. Looking up a notcurses struct from an
ncpile doesn't seem to happen frequently enough that the extra
pointer deref would have much effect on performance.
4) A new flag will be added to ncplane_options, NCPLANE_OPTION_NEWPILE,
creating the new ncplane on a new ncpile.
This allows the cleanest creation of a pile, when it's known
that a new plane is intended to start one. Extracting a plane
from an existing pile is going to have some overhead, as we'll
see below.
5) An ncplane reparented to itself becomes the root plane of a new
pile, unless it is already a root plane, in which case the
reparenting is a no-op. Bound planes and siblings do not join it
in the new pile. The new zaxis contains of one member.
This action is currently a no-op in all cases. Since a plane
parented to itself is a root plane, this makes total sense as an
expansion of the funtion. Creation of and extraction from zaxes
is O(1).
6) A new function, ncplane_make_sibling(), will be added.
This allows an ncplane to be made a sibling of another.
ncplane_reparent(ncplane_parent(A)) doesn't work if A is a root
plane (sadly), else this would be mere semantic sugar. This
function is being added to cover the case where we want to make
a plane part of the root set of a pile. I imagine this will be a
very rare event, and hesitate to add this function, but it
doesn't make anything more complex -- it's just something of a
wart.
An alternative would be to have root planes return an ncpile as
their parent, to which one could reparent a plane. This has
several downsides: it exposes ncpile, it requires
ncplane_parent() to return either an ncplane or an ncpile, and
it requires ncplane_reparent() to accept either an ncplane or an
ncpile. I feel the approach of ncplane_makesibling() is less an
overall wart.
A second alternative would be to say "fuck it" and not introduce
this function at all. That's such a hit to conceptual simplicity
that I can't countenance it. But maybe I'm missing something...?
Note that a sibling is also created via ncplane_dup().
7) A new function, ncplane_reparent_family(), will be added. This
function works the same way as ncplane_reparent(), except that
it brings along any bound planes.
This is an extension of what already exists after implementing
(5), since the current ncplane_reparent() does not bring along
bound planes (they are rebound to the plane's original parent).
Note that extracting child planes, if they exist, requires a
traversal of the originating zaxis having both O(N) time and
O(N) state--a semi-expensive operation. Piles are ideally
created at ncplane_create() time, and operated on from there.
When reparenting a family within the same pile, there's no need
for these O(N) operations, as the zaxis is not changed.
This is entirely orthogonal to the overall goals of this change,
and who knows, maybe we won't do it.
8) Reparenting an ncplane to an ncplane within another pile places
it immediately above the new parent on the zaxis. Reparenting an
ncplane as a family sees the same behavior, with all moved
children placed atop the reparented plane, retaining their
z-order from the source pile.
There's no logic to where we place the reparented plane within
the new pile's zaxis, so we pick a place -- above the new
parent. The most reasonable alternatives would be either the top
or bottom of the new zaxis. There's no real reason to pick any
of them -- it's an O(1) splice no matter what -- and this seems
most natural.
Just as they do now, bound planes are reparented to the parent
of the reparented plane. If the reparented plane is a root
plane, any bound planes now become root planes.
9) When no references exist to an ncpile, it is destroyed.
This is one reason to keep the ncpile struct hidden -- we know
there are no references outstanding once we detach the last
ncplane. This doesn't require reference counting or anything
like that; we just kill the pile when a plane which is all of a
root, childless, and siblingless is detached.
10) notcurses_render() is loosely deprecated, and operates on the
standard plane's pile.
We will deemphasize notcurses_render(), but there's no immediate
need to get rid of it.
11) ncpile_render_buffer() will be added, taking as its argument an
ncplane, and operating on its pile.
Pretty self-explanatory. I prefer this to ncplane_render_buffer() to
emphasize that we start rendering at the pile's top plane, not at the
provided plane. ncpile_render_buffer() called on any plane from
the standard pile is equivalent to notcurses_render_to_buffer().
12) It is an error to concurrently rasterize rendered buffers,
including rasterizing one while calling notcurses_render()
(which implicitly rasterizes).
I should hope that the reasoning for this is obvious. I list it
primarily to emphasize that rasterizing buffers in a different
order from how they were rendered is perfectly legal, since the
rasterization optimizations based on the currently-rendered
state are not relevant to the process of rendering.
13) notcurses_stop will continue to clean up all state.
No need to manually ensure all ncplanes are destroyed;
notcurses_stop() continues to handle this.
14) It is legal to concurrently mutate distinct piles in any way
one might dream.
The entire point of this exercise. This mainly just means we
don't want to have any concurrently-accessed global list of
ncpiles, nor any data structure that contains planes from
multiple piles. I think we need to have the former to ensure
proper notcurses_stop() cleanup; that's fine, we'll just throw a
lock around it (mutating this list will be a rare operation).
This list will take the form of a doubly-linked list to ensure
O(1) splicing.
This seems entirely backwards-compatible with the old school
(save that ncplane_reparent() now has an action for what was
previously a no-op (but silly) case). I'm willing to break
people who were relying on this no-op (a survey of known
Notcurses projects does not suggest that anyone is). It adds
very little overhead:
state: three 64-bit pointers per pile
time: only O(N) operation is extracting the planes from a pile's
zaxis when calling ncplane_reparent_family()
yet opens up a bold new world of parallelism and flexibilty, and
doesn't complicate the way for #1109 (at which time we'll have a
fully Copernican universe).
https://www.youtube.com/watch?v=RgtNuhOH2q8
--
nick black -=- https://www.nick-black.com
to make an apple pie from scratch,
you need first invent a universe.
Reply all
Reply to author
Forward
0 new messages