GitLab

I'm wary as heck at introducing any amount of abstraction in
benchmarks, because sometimes, it starts to foment lies in the
most unexpected ways.  However, I did several fairly long runs
with and without this contraction, and they seem to vary on the
order of single nanoseconds -- while the noise between test runs
varies by a few dozen.  So, this appears to be safe to move on.

(This is the new feature I just merged all those library version
bumps to enable.)

Be aware I'm using the go mod files blindly, and actually testing and
developing using the git submodules.

I actually only wanted one update here -- the go-wish library bump,
for a specific new feature I wanted for some work on another branch --
but as long as I'm here, apparently all these bumps break nothing.

Includes duplicate key checks that were previously missing.

Overall, checks many more invariants.  There are now "*_ValueAssembler"
types involved in both the 'free'/generic implementation, and the
codegen implementation: in both cases, it's needed for several tasks,
mostly revolving around the "Done" method (or anything else that causes
doneness, e.g. any of the scalar "Assign*" methods):

- to make sure the map assembly doesn't move on until the value
  assembly is finished!  Need to do this to make it possible to
  maintain any other invariant over the whole tree!
- to do state machine keeping on the map assembler
- to do any integrity checks that the map itself demands
- and in some cases, to actually commit the entry itself (although
  in some cases, pointer funtimes at key finish time are enough).

The introduction of these '*_KeyAssembler' and '*_ValueAssembler' types
is somewhat frustrating, because they add more memory, more vtable
interactions (sometimes; in codegen, the compiler can inline them out),
and just plain more SLOC.  Particularly irritatingly, they require a
pointer back to their parent assembler... even though in practice,
they're always embedded *in* that same structure, so it's a predictable
offset from their own pointer.  But I couldn't easily seem to see a
way around that (shy of using unsafe or other extreme nastiness), so,
I'm just bitting the bullet and moving on with that.

(I even briefly experimented with using type aliases to be able to
decorate additional methods contextually onto the same struct memory,
hoping that I'd be able to choose which type's set of methods I apply.
(I know this is possible internally -- if one writes assembler, that's
*what the calls are like*: you grab the function definition from a
table of functions per type, and then you apply it to some memory!)
This would make it possible to put all the child assembler functions
on the same memory as the parent assembler that embeds them, and thus
save us the cyclic pointers!  But alas, no.  Attempting to do this will
run aground on "duplicate method" errors quite quickly.  Aliases were
not meant to do this.)

There's some new tests, in addition to benchmarks.

'plainMap', destined to be part of the next version of the 'ipldfree'
package, is now complete, and passes tests.

A couple key tests are commented out, because they require a bump in
version of the go-wish library, and I'm going to sort that in a
separate commit.  They do pass, though, otherwise.

Some NodeStyle implementations are introduced, and now those are the
way to get builders for those nodes, and all the tests and benchmarks
use them.  The placeholder 'NewBuilder*' methods are gone.

There are some open questions about what naming pattern to use for
exporting symbols for NodeStyles.  Some comments regard this, but it's
a topic to engage in more earnest later.

Benchmarks have been renamed for slightly more consistency and an eye
towards additional benchmarks we're likely to add shortly.

Some new documentation file are added!  These are a bit ramshackle,
because they're written as an issue of note occurs to me, but there are
enough high-level rules that should be held the same across various
implementations of Node and NodeAssembler that writing them in a doc
outside the code began to seem wise.

It does not.

I turned benchtime up to 15s because in 1s runs, any signal was well
below the threshhold of noise.  And even with larger sampling:

```
BenchmarkFeedGennedMapSimpleKeys-8                      39906697               457 ns/op             400 B/op          5 allocs/op
BenchmarkFeedGennedMapSimpleKeysDirectly-8              39944427               455 ns/op             400 B/op          5 allocs/op
```

It's literally negligible.

It's still possible we'll see more consequential results in the case of
structs, possibly.  But from this result?  I'd say there's pretty good
arguments made *against* having the extra method, here.

More costly than I expected.

New results:

```
BenchmarkBaselineNativeMapAssignSimpleKeys-8             5772964               206 ns/op             256 B/op          2 allocs/op
BenchmarkBaselineJsonUnmarshalMapSimpleKeys-8             470348              2349 ns/op             672 B/op         18 allocs/op
BenchmarkFeedGennedMapSimpleKeys-8                       2484633               446 ns/op             400 B/op          5 allocs/op
```

Okay, so our wall clock time got worse, but is still flitting around
2x; not thrilling, but acceptable.

But apparently we got a 5th alloc?  Ugh.

I looked for typos and misunderstandings, but I think what I failed
to understand is actually the interal workings of golang's maps.

The new alloc is in line 343: `ma.w.m[ma.w.t[l].k] = &ma.w.t[l].v`.
As scary as that line may look, it's just some pointer shuffles;
there's no new memory allocations here, just pointers to stuff that
we've already got on hand.  Disassembly confirms this: there's
no `runtime.newobject` or other allocations in the disassembly of
the `flushLastEntry` function.
Just this salty thing: `CALL runtime.mapassign_faststr(SB)`.
Which can, indeed, allocate inside.

I guess what's going on here is golang's maps don't allocate
*buckets* until the first insertion forces them to?
Today I learned...

Memory works like I think it does.  That's good.

Added a third entry just to make some numbers odd and effects a wee
bit more visible.

Fixed the map to do allocs up front using the size hint; and rather
importantly, actually return the embedded child assemblers.  (Those
are... kinda an important part of the whole design.)  And that got
things lined up where I hoped.

Current results:

```
BenchmarkBaselineNativeMapAssignSimpleKeys-8             5665226               199 ns/op             256 B/op          2 allocs/op
BenchmarkBaselineJsonUnmarshalMapSimpleKeys-8             519618              2334 ns/op             672 B/op         18 allocs/op
BenchmarkFeedGennedMapSimpleKeys-8                       4212643               291 ns/op             192 B/op          4 allocs/op
```

This is what I'm gunning for.  Those four allocs are:

- One for the builder;
- one for the node;
- and one each for the internal map and entry slice.

This is about as good as we can get.  Everything's amortized.
And we're getting ordered maps out of the deal, which is more
featureful than the stdlib map.  And the actual runtime is pretty
dang good: less than 150% of the native map -- that's actually
better than I was going to let myself hope for.

We're *not* paying for:

- extra allocs per node in more complex structures;
- extra allocs per builder in more complex structures;
- allocs per key nor per value in maps;
- and I do believe we're set up even to do generic map iteration
  without incurring interface boxing costs.

Nice.

I haven't begun to look for time optimizations at all yet;
but now that the alloc count is right, I can move on to do that.

There's also one fairly large buggaboo here: the values don't
actually get, uh, inserted into the map.  That's... let's fix that.

(Thank goodness.  Been in theoryland for a while.)

There's somewhat more content here than necessary for the benchmark
that's presently runnable; right now only the Map_K_T implementation
is targetted.  I want benchmarks of things with complex keys in codegen
and also benchmarks of the runtime/generic/free impls soon, so
they can all be compared.

There's also a quick fliff of stdlib map usage in a wee benchmark to
give us some baselines...

And there's also a quick fliff of stdlib json unmarshalling for the
same reason.  It's not fair, to be sure: the json thing is doing work
parsing, and allocating strings (whereas the other two get to use
compile-time const strings)... but it sure would be embarassing if we
*failed* to beat that speed, right?  So it's there to keep it in mind.

Some off-the-cuff results:

```
BenchmarkBaselineNativeMapAssignSimpleKeys-8             6815284               175 ns/op             256 B/op          2 allocs/op
BenchmarkBaselineJsonUnmarshalMapSimpleKeys-8             724059              1644 ns/op             608 B/op         14 allocs/op
BenchmarkFeedGennedMapSimpleKeys-8                       2932563               410 ns/op             176 B/op          8 allocs/op
```

This pretty good.  If we're *only* half the speed of the native maps...
that's actually reallyreally good, considering we're doing more work
to keep things ordered, to say nothing of all the other interface
support efforts we have to do.

But 8 allocs?  No.  That was not the goal.  This should be better.

Time to dig...

per comment in previous commit, it's time to aim towards executable
benchmarks again.

We really, truly cannot get away from having a KeyAssembler option.
That much seems clear.  So that's moved up into the interface we're
working with, and one of the alternate drafts dropped.

The comments around the NodeBuilder.Reset method are resolved: the
parts about building keys are removed, as we've concluded pretty
solidly that those were indeed about to take a wrong turn.
(Resetting a builder is still a useful thing overall if you're going
to make a bunch of nodes of a single type: the node allocations
will still happen, but the builder being resettable should be
pretty much a giant duff's device action, and saves one of the
two mega-amortized allocations in a codegen'd world, which is better
than not.)

Dropped the "demo" function.  This isn't the place for it, and that
demo had also gone awry.

Some new questions about some of the other "simple" methods on
MapAssembler and ListAssembler.  Are they useful shortcuts (that
actually provide a performance benefit if present directly on the
assembler interface)?  Or are they trivially recreateable from a
freestanding function operating the interface, and thus better be
done that way, to save SLOC in codegen outputs?

I think I'm going to start needing benchmarks to come to useful
conclusions on that last question pair, so... it's time to move forward
on writing some more implementation code matching these interfaces.
(Unfortunately, I think there's at least... four different
implementations needed to get a good eye on things, since the codegen
path vs runtime fully generic interfaces path have *very* different
characteristics, and then we need each of the styles of interest
implemented for each.  But that's just what we'll have to do.)

This is one of those situations where I'd really, really, really love
to be able to state default values for method params.  And I don't see
who could possibly be hurt by such a language feature, so I'm sad we
don't have it.

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>

Feat/add code gen disclaimer

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

Add a disclaimer to the header for generated code to prevent linters from complaining

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.