GitLab

Hopefully to become final.  I'm going to try to copy the contents out
to the root dir to become the new interfaces at the end of this.

I copied most of the node.go file and it's probably best to read that
as a diff from the live one.  Mostly, it adds the NodeStyle type
and the documentation around that.

The nodebuilder.go file still devolved into some commentstorms and
incomplete parts, but is probably honing in on minimally-unsatisfying
compromises.

I used a couple symlinks to "copy" the types for Path, etc, from the
live main package, just to get more things compiling together.
Those features aren't showing any cracks and aren't up for review due
to any transitive interactions that are in question, so, this treatment
is sufficient to move things along.

Links aren't present in the package yet.  I may or may not do some
reconsiderations on those to match the "style" naming pattern, as the
'nodestyle' research package already briefly probed; or, it might be
out of scope and something for later (if at all).  This is a presently
a compile error until I handle it one way or the other.

The long-story-made-short of the remaining commentstorm is: handling
map keys generically just absolutely sucks.  There is basically no
way to do it without massive allocation penalties for boxing.  Any and
all alternative tradeoffs I can think of are baroque and not pleasing.
I'm still hoping for another idea to strike, but at this point it's
looking like it's time to bite some bullet (any bullet) and move on.
Signed-off-by: Eric Myhre <hash@exultant.us>

Signed-off-by: Eric Myhre <hash@exultant.us>

Not all of these compile.  I'm going to try to blaze through this and
the rest of the experiments until we get to a result quickly, and
probably then promptly remove most of these directories.  Meanwhile,
since we're under a path prefix beginning with an underscore, build and
test commands using the "./..." don't trip here.

There's at least one thing seriously wrong with each of these drafts,
and each of them also devolves into comments rather than completion,
but I think they're getting closer to circling around something useful.
Signed-off-by: Eric Myhre <hash@exultant.us>

And expand on the need for both general and specific methods, even
though they both can accomplish the same goals.

See the comment blocks at the top of the file for reasons why.

See the comment blocks at the bottom for some remarks on the outcomes.

tl;dr it's certainly *differently* frustrating than the current
interface, if nothing else!  Better?  I dunno.  Maybe!

I'm still scratching out prototypes in another directory to make it
easier to focus on the details I'm interested in rather than get
wrapped up with the kerfuffling details of the existing full
interfaces... as well as easier to try out different interfaces.
And at some point, of course, we want *codegen* for these things, while
what I'm plunking about with here is a sketch of the expected *output*.
So, this is a large step removed from the final code... but it's easier
to sketch this way and "imagine" where the templating can later appear.

This solution approach seems to be going largely well.

And we have some tests which count allocs very carefully to confirm
the desired result!

Still a lot to go.  There's large hunks of comments and unresolved
details still in this commit; I just need a checkpoint.

Some things around creation of maps are still looking tricky to
support optimizations for.  Research needed there.  A comment hunk
describes the questions, but so far there's no tradeoff-free answer.

Perhaps most usefully: here's also a checkpoint of the
"HACKME_memorylayout" document!  It also still has a few todos, but
it's the most comprehensive block of prose I've got in one place
so far.  Hopefully it will be useful reading for anyone else wanting
to get up to speed on the in-depth in "why" -- it's awfully,
awfully hard to infer this kind of thing from the eschatology of
just observing where pointers are in a finished product!
Signed-off-by: Eric Myhre <hash@exultant.us>

As you can see from the directory name ("multihoisting"), when I began
exploring this topic, I didn't know they were called that.  :/
This thus turned out to very much be one of those occasions where
knowing the *right two words* to put into a search engine would've
saved a fairly enormous number of hours.  Once I finally found the
right term, some perfectly lovely documentation appeared.  But alas.

(Like the previous commits, this stuff is coming from a while ago;
roughly Oct 25.  It uncovers a lot of stuff that gets us much closer to
being able to make correct and performant designs to minimize and
amortize the number of allocations that will be required to make our
node trees work in codegen (though with that said, there will also
still be plenty of details in need of refinement after this, too).)

Still working on a "HACKME_memorylayout.md" doc, which will appear
in the codegen directories in the near future and contain a summary
of these learnings and how they balance against other design concerns.

Meanwhile, a couple of other notes in their rough form:

- basically, don't use non-pointer methods.
	- turns out value receivers tend to mean "copy it", and pointer receivers *don't* mean "heap alloc it" (they just mean "consider escape, maybe").
		- so overall you're tying the compilers hands when you use a value receiver, and you're *not* when you use a pointer receiver.
- taking pointers to things already being passed around in pointer form or already having heap-escaped seems to be free.
	- it might demand something become heap alloc if it wasn't already...
		- but this turns out to be fairly amortizable.
		- because if you write nearly-everthing to be pointers, then, there you go.
	- and if you're lucky and something is shortlived (provably doesn't escape), then even whole stacks of ptr-receiver methods will still probably inline and collapse to no heap action.
		- the analysis on this seems to reach much further than i thought it would.
		- `-gcflags '-m -m'` was extremely revealing on this point.
- tl;dr:
	- more pointers not less in all functions and passing;
	- but do have one struct that's the Place of Residence of the data without pointers.
	- this pair of choices probably leads to the best outcomes.
- hokay so.  applied to topic: two sets of embeds.
	- builders might as well have their own big slab of embed too.
		- logically nonsense to embed them, but incredibly rare you're not gonna use the memory, so!

And a couple important incantations, which can help understand
What's Really Going On Here in a bunch of ways:

- `-gcflags '-S'` -- gives you assembler dump
- `-gcflags '-m'` -- gives you escape analysis (minimally informative and hard to read)
- `-gcflags '-m -m'` -- gives you radically more escape analysis, in stack-form (actually useful!!)
- `-gcflags '-l'` -- disables inlining!

I learned about the '-m -m' thing by grepping the Go compiler source,
incidentally.  It's a wildly under-documented feature.
No joke: I encountered it via doing a `grep "Debug['m']` in go/src;
there is currently no mention of it in `go tool compile -d help`.
Once I found the magic string, and could submit it to search engines,
I started to find a few other blogs which mention it... but I'd
seen none of them (and had not found queries that turned them up)
until having this critical knowledge already in-hand.  >:I
So chalking up another score for "the right words would've been nice".

Performance work is fun!

This is... a set of changes of mixed virtue.

The codegen won't stay in this state for long.  Things have been
learned since this was drafted.  This diff uses value methods
heavily, and those are... mostly a bad idea, big picture.

But it's got some incremental progress on other things, so I'm
going to fold it into history rather than drop it.

It's been, broadly speaking, "tricky" to plan out and design some of
this project.  It's been doubly tricky to do it while understanding
the holistic performance implications of the detailed choices.
And while "premature optimization, evil", etcetera... I've gone
through the performance rodeo in this vincinity at least once before
(in the form of the refmt libraries): and resultingly, I'm going to
claim a slightly-better-than-zero intuition for what's premature and
what's utterly critical to keep track of as early as possible lest
ye be doomed to a rewrite after learning things the hard way.

(Arguably, half this codebase **is** the rewrite after learning things
the hard way.  But I digress.)

So: to combat this "trickiness", I've started writing a lot of
"research" code and experimental benchmarks.
This is still certainly fraught with peril -- in fact, one of the
major things I've learned overall is just *how* dangerously misleading
microbenchmarks can be (and to combat this, I've now started regularly
reading the assembler output to make sure the optimizer is doing
exactly what I think it is, neither more nor less) -- but it's much
more informative than *not* doing it, and trying to suss out the mess
later once you've built a whole system.

And that's what it's time to start committing.
(I should've started a while ago, honestly.)

This "rsrch" directory will get some more content momentarily in
coming commits, because there's a *lot* of stuff on my localhost.
Some of it was so preliminary I'm not going to bother to preserve it;
a lot of things are potentially pretty interesting, as educational
and archeological material, if nothing else: those I'm going to commit.

(It's possible all this will end up `git rm` again at some time in the
future, too.  But honestly, it's darn hard to remember "why didn't
you just do X?" sometimes.  Notes need to get committed *somewhere*,
at least briefly enough that it's possible to dig them out again.)

So!  To start: here are some research benchmarks into what strongly-
natively-typed builders might look like in our codegen outputs.

These are from about Oct 13th, as best I can suss localhost mtimes.
I think most of these concepts are ones I'm (frustratingly) backing
away from now, because I've learned a *lot* more about performance
in the meanwhile, and I don't think these are gonna do well.
But the worked exploration into ergonomics is still potentially
interesting and worth review!
Signed-off-by: Eric Myhre <hash@exultant.us>

The readme hadn't seen an update for quite a long time, so it was just
overdue for it.  I think the comments about where to expect changes
at this point are practically accurate and now are also stated.

The Node interface, despite being so central to the entire system,
was missing a doc block on the type as a whole!  It now has one.
(I'd like to continue to iterate on this and have it do more linking
out to ipld docs for some of the more conceptual parts, but we've
got a lot of work to do on that content as well, so, for now just
doing it here is better than not having it.)
Signed-off-by: Eric Myhre <hash@exultant.us>

fix(schema/gen): return value not reference

Map/List should return an actual node type, not a pointer to a node. Otherwise, breaks when nested
in other map/list type

Using pointers for optional or nullable fields forces a lot of things
to need allocations on the heap.  And maybe that's not so good.

So here's a very different take.  'Maybe' structures for any
optional or nullable fields store the extra information about
null or absent values.

This takes more linear memory... but should tend to result in fewer
allocs.  It's also much easier to code against, I suspect.
(And we expect it's not unreasonable for users to add more methods
in the generated output package, which would mean we should be
believable to code against.)

feat(schema/gen): make emit methods public

Make emit methods public to allow a preliminary method for generating code outside this module

Signed-off-by: Eric Myhre <hash@exultant.us>

Rearrange to match 68b3383d,

and add methods to match 41d79374.

Everything compiles again, and resultant code passes what tests it has.
Signed-off-by: Eric Myhre <hash@exultant.us>

(n.b. I've already tried implementing the suggested thing for structs,
but won't link to it here as that commit is almost certainly going
to end up rebased.  Jury's still out on if the idea is good or not.
Seems like the answer is almost certainly "it depends".)

(I don't like doing nontrivial work in a merge commit, because many git
UI's don't show them well, so it will be in subsequent commits;
and this one is thus (unavoidably) broken.)

This is missing substantial amounts of context (it's really only
compared to other benchmarks *out of the repo*, as the comments note),
but it's been sitting on my hard disk for a while, so it might as well
be committed.
Signed-off-by: Eric Myhre <hash@exultant.us>

must: an alternative mechanism for fluent calls.

See the package docs string for explanation.
Signed-off-by: Eric Myhre <hash@exultant.us>

add int, bytes, and link types to code-gen

fill in generated type for list

Fill in generated types for int, link, and bytes nodes

feat(selectors): support union limit type

Refactors the limit data on recursive selectors to be a union type

switch maxDepth on ExploreRecursive to union limit type per spec

The previous names started to seem more questionable as we start
generating additional code which is natively typed rather than
interface constrained.  Now the latter stuff is in a file that
includes 'Node' as part of the filename.  This seems better.

This introduces several new methods to the type generator.
The new comment at the top of 'gen.go' explains the direction.

There are several (sizable impact) TODOs in the methods for structs;
this is because some other research I've been doing on performance
is going to result in a re-think of how we regard pointers,
and a *lot* of the struct code is going to get a shakeup shortly.
Should be coming up in about two commits or so.
(The 'Maybe' structs getting their first mention here will have
something to do with it!)

Some more file split-ups to keep node interface generation separate
from native-typed API generation will be coming up next commit.

You can also see here some TODOs regarding the future possibility of
"validate" methods.  This is something I want to pursue, but the
implementation work will be nontrivial -- those TODOs will probably
stay there a good while.
Signed-off-by: Eric Myhre <hash@exultant.us>

Child-builder recursion; and typed unmarshal over codegen native structs.

(At long last!  These child-builder methods are a step that was known
to be needed for some time now, but I've intentionally been pushing off
the implementation of it until we finally reached some *other* piece of
functionality that would depend on it and force the issue.  Finally,
that's happened: that issue is unmarshalling into natively-typed
codegenerated nodes, and that's now.  Woo!)

(Though the current focus of this is for natively-typed codegen'd nodes,
if we put further effort into reflective-bind node implementations,
they'll also lean heavily on these child-builder-getters for internally
tracking the correct `reflect.Type` to create new values of -- very
similar to what our schema-typed things are doing, just with the Golang
type system instead of our schema types.)

The child-builder getter methods more or less explain themselves.
They yield a new NodeBuilder that's correctly specialized for child
nodes in recursive structures.  This is necessary for both keys and
values in maps, and for values in lists.  For values in lists and maps,
getting the child-builder requires takes a parameter -- this is so
typed nodes (namely, structs; but some unions will also lean on this)
may have discriminated contents that differ per key or index.

The BuilderForValue functions are able to take primitive strings and
ints as parameters rather than Node, because all uses that have
discriminated results are places where complex keys are not acceptable.
Therefore primitives are fine, and preferred since it avoids boxing.

The 'free' node implementation is updated to include this feature,
as are codegenerated nodes.
(The runtime wrapper typed node implementations have partial support,
but stubbed methods where the path forward is clear but the
implementation effort nontrivial and not currently on-priority-path.)

Unmarshalling now uses these child-builder-getters to correctly handle
the passing down of constraints and typeinfo.  This addresses several
TODO's that have been in the unmarshalling code for aeons -- hooray!
(Somewhat remarkably, our solution here is much better than the one
proposed in those ancient TODO's -- we actually got this done *without*
direct abstraction-breaking examination for typed nodes.  Nice!)

Unmarshalling tests are also in this same diff.
There's even a wee little benchmark using a snippet of JSON as fixture.
This is the first time we see unmarshalling and marshalling end-to-end
connected with codegen'd nodes.  This is very exciting!

There's still some questions to be answered about the most correct
(and most performance-friendly) place to put error handling against
asks for a child NodeBuilder with an invalid key or index, which is
a very real invalid state that's reachable for typed nodes that are
structs.  Comments about that are inline in the diff.  We'll probably
have to come back to that soon, but I'm gonna let it stew on the
back burner for a bit.  Currently, panics are used, but this may not
be acceptable ergonomics.

---

It's somewhat effortful to even detail how many thoughts about
performance and the future optimization potentials go into this diff.
Some comments I had in the area of the child-builder specialization
functions included concerns on:

- where common-subexpression-elimination will and won't apply
- where inlining is possible vs facing function call stack shuffle overhead
- ... as well as how that affects common-subexpression-elimination
- ... as well as how that affects escape analysis and shifts to heap
- whether an isDiscriminated property will make any of these things better
- can BuilderForValue hang onto a builder, boxed into interface already, when appropriate?
- ... for the maps case, should amortize in a way comparable to isDiscriminated, yes?  verify.
- ... can we do that without the builder keeping another two words of memory just... around?  i don't think so.  question is if it pays for itself.
- question: do zero value no-fields structs get a bonus?  reading runtime/iface.go -- doesn't look like it.  but needs confirmation.
- ... revised statement: they do, it's just nonobvious.  iface.go doesn't have a specialization, but the mallocgc call hits a special path internally for zero, and then the typedmemmove call 'coincidentally' hits its "src == dst" short-circuit, thus also being fast.

... all in all, as many of these as possible of these concerns have
been considered and this design should be optimization-friendly;
some of them are bucketed into "we'll see", because we need to build
nontrivial programs to see how significant the needs are, as well as
to see how clever the compiler can get with what we've already done.

There are some possible alternative ways we might re-engineer the
builders in the future to make them more performance-friendly.
In particular, the fact that many builders carry a previous value
with them in anticipation of one of the 'Amend' calls -- which is
not necessarily going to be used! -- is a potential obstruction to
optimization, since it makes many structures go from zero to
more-than-zero size, and that hits significantly different paths
in the runtime with very different performance characteristics.
However, that is a bit much to change today; so the thought lives
here as a note for potential future work.

Adding a `BuilderForValueIsDiscriminated() bool` method later seems
still seems on the table, but since it wouldn't require substantial
restructurings or headaches, can be deferred until benchmarks show
us exactly how much it matters.
(A single `type ChildBuilders interface { Style() Complexity; ... }`
with some enum for `Compleixty` resembling
`SimpleList | SimpleMap | DiscriminatedMap | DiscriminatedList` might
also be a tempting way to go about this.)

---

An alternative design considered that deserves a quick note: we
could've added a `ChildBuilders()` method to the MapBuilder and
ListBuilder, and attached the further getter methods there.
This might still be viable, if we found that there are more methods
involved in the future and we want to group them: it *should* always
land on the zero-fields struct path, which means it can be done
without hitting an expensive malloc.  However, at present this doesn't
seem warranted: we don't have enough methods to make it feel important
(especially after the recognition that Node variants of methods aren't
needed in addition to the primitive args variants, described above).

---

Whew.

Lines of code in diff does not correlate to hours of thought required.

Glad to have this landing.  Even performance minutae aside,
there was a significant period of time where I was terrified that all
these abstractions were going to shatter magnificently when it came
time to do the final end-to-end unification of all this massive arc
of work.  But now it's done.  And it works.  Whew.

Next: more fleshing out of more types; perhaps more benchmarks; and
also it's time to do some more drafts of the native accessors and
builders.  Some of that already has been done in parallel in gists
while this diff was incubating, but it's time to commit it too.

Noticed due to the previous commit adding this need to the listbuilder;
but the maps have been quietly wrong for a while now.  Eep.
Signed-off-by: Eric Myhre <hash@exultant.us>