GitLab

See comments in that commit.  It's a good idea, but needs some further
refinement in order to really shine.

It's possible, but this is a bit less trivial than it sounds...
so I think this is one of those diffs I'm going to *save*, but
via a "merge-ignore", and come back to the topic again later.

Here's where we were at before this diff:

```
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=0-8    3882726               308 ns/op             448 B/op          5 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=1-8    1273840               961 ns/op             464 B/op          6 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=2-8     690142              1785 ns/op             624 B/op          8 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=4-8     376281              3197 ns/op             944 B/op         11 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=8-8     197530              6084 ns/op            1584 B/op         16 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=16-8    102693             11534 ns/op            2864 B/op         25 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=32-8     54110             22601 ns/op            5424 B/op         42 allocs/op
```

(This is still a very sizable improvement over the node implementations on master;
about double the speed and a quarter of the allocs.  But still, could be improved?)

With this diff adding iterator amortization (and a bench loop with timer pauses in it):

```
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=0-8            1580808               778 ns/op             432 B/op          4 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=1-8             744278              1574 ns/op             432 B/op          4 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=2-8             468837              2529 ns/op             576 B/op          5 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=4-8             277303              4171 ns/op             864 B/op          6 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=8-8             172590              7187 ns/op            1440 B/op          7 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=16-8             93064             12494 ns/op            2592 B/op          8 allocs/op
BenchmarkSpec_Marshal_MapNStrMap3StrInt/n=32-8             52755             22671 ns/op            4896 B/op          9 allocs/op
```

So... this is kind of an unexpected result.  We got the allocs to go down,
as intended.  But speed didn't go up.  What gives?

A priori, I've been running with the ballpark number of "88ns per alloc"
(derived from some other observations on these packages today), which...
would lead me to compute an expected gain in speed of about `88*(42-9)`
given how many fewer allocations we see here... which in turn would lead
to an expectation of about 12.8% speed improvement.
Which... we don't see at all.  The speed is more or less unchanged.
Hrm.

I suspect that the reason for this is that having StartTimer/StopTimer
calls in the middle of your `b.N` loop just is not possible to do without
having serious skewing effects on results, and if we could clear away
the skew, we'd probably see the expected improvement.

But still, in light of this unclarity, I'm going to merge-ignore this.
We can come back to this optimization later.
After this reflection, I feel ~12% isn't worth chasing today,
especially if it's a complicated 12%, and especially since we already
have other much larger effects that are still in progress of getting
properly landed and into use on the master branch.

Another issue that deserves due consideration is how this change would
interact with concurrent use of datastructures.  Since nodes are
immutable, we *should* usually be able to expect that they can be read
across threads without issue.  This patch would break that: getting
two different iterators could be a race condition.  Fixing this is easy
(I'd use https://golang.org/pkg/sync/atomic/#CompareAndSwapUint32),
but raises the scope just a bit, and files this further as "not today".

Iterators might also deserve a "Close" method in order to make this
kind of optimization more accessible to the user; there's no reason it
has to be once-only.  (This would also just so happen to fix the reason
we needed StartTimer/StopTimer in the b.N loop, making measurement of
the improvement easier.)

Lots of things to consider when tackling this properly in the future!

Sizable performance impact.

Recently added scalable benchmarks helped point this out.

(Arguably, certainly, I could've/should've seen this one earlier; it's
honestly pretty "duh".  But somehow it never got priority attention.
A benchmark is still awfully useful for directing attention!)

With this, the new node marshal is looking *really* snazzy.
Most of the allocations remaining there are just iterator creation...
and we have a plan to amortize those out of existence, too.
But I'm going to save that one for later.

Marshal is 25% faster.  Not bad.  (There's also a perf bug in the codec
code which I'm about to fix which will change the speedup to *double*.)

Unmarshal is a bit faster, but not as much improved as marshal.
This is unsurprisingly because we chose not to amortize allocations
as much as we could in map and list creation because the size penalty
seemed too steep to make it a worthy trade.  (This gives us *much*
better numbers to fuel further consideration of that trade, though.)

Dear reader, I am so excited about this.

Also: added additional sanity checks to the end of benchmarks, after
a call to `b.StopTimer`.  Always important to make sure your benchmark
is actually doing what you think it is, and not being super fast
because it turns out to be a hyperspeed application-layer devnull!

(In the case of the unmarshal tests, asserting sanity by remarshalling
the whole dang thing *again* might look a little funny... but it's
certainly a terse way to get full coverage of the data!)

This is one of the key goals I've been trying to work toward with all
the fixture nomenclature efforts.  (Correspondingly, finally this is
a naming pattern I'm satisfied with, as well.)

Here's an example output, from the ipldfree package:

```
BenchmarkSpec_Walk_Map3StrInt-8                          1501033               802 ns/op             624 B/op          9 allocs/op
BenchmarkSpec_Walk_MapNStrMap3StrInt/n=0-8               6288885               191 ns/op              96 B/op          3 allocs/op
BenchmarkSpec_Walk_MapNStrMap3StrInt/n=1-8               1000000              1160 ns/op             896 B/op         13 allocs/op
BenchmarkSpec_Walk_MapNStrMap3StrInt/n=2-8                520072              2326 ns/op            1696 B/op         23 allocs/op
BenchmarkSpec_Walk_MapNStrMap3StrInt/n=4-8                239588              4293 ns/op            3296 B/op         43 allocs/op
BenchmarkSpec_Walk_MapNStrMap3StrInt/n=8-8                138903              8461 ns/op            6496 B/op         83 allocs/op
BenchmarkSpec_Walk_MapNStrMap3StrInt/n=16-8                70845             16951 ns/op           12896 B/op        163 allocs/op
BenchmarkSpec_Walk_MapNStrMap3StrInt/n=32-8                33601             33793 ns/op           25696 B/op        323 allocs/op
```

This roughly linear increases in time taken and in allocs required as
the size of the data we walk is increased.

(What I'm hoping to see when we land the NodeAssembler refactor and
other key improvements to reduce interface boxing costs that were
co-developed with that change is: we'll see the allocs become O(1),
and the linearity on the time will become a much less sharp incline!)

I suspect one could parse these names back apart to draw graphs for
the various sizes.  (I think such tools exist out there already, though
I don't have a working knowledge of them yet.  If something suitable
doesn't exist already, the basic pieces to assemble something do:
https://github.com/golang/perf/blob/36b577b0eb03b831f9f591c1338a115cafcb56a7/storage/benchfmt/benchfmt.go#L31
has a parser for the output format.)

We should also be able to reuse these benchmarks for other Node
implementations fairly effortlessly.  I'm particularly looking forward
to seeing how that shapes up when we apply it to codegen'd stuff.

In the future, I want to rack up even more data in name patterns like:

 baselines.BenchmarkSpec_Unmarshal_MapStrInt/codec=json/n=3
 baselines.BenchmarkSpec_Unmarshal_MapStrInt/codec=json/n=25
 basicnode.BenchmarkSpec_Unmarshal_MapStrInt/codec=json/n=3
 basicnode.BenchmarkSpec_Unmarshal_MapStrInt/codec=json/n=25
 basicnode.BenchmarkSpec_Unmarshal_MapStrInt/codec=cbor/n=3
 basicnode.BenchmarkSpec_Unmarshal_MapStrInt/codec=cbor/n=25
   gendemo.BenchmarkSpec_Unmarshal_MapStrInt/codec=json/n=3
   gendemo.BenchmarkSpec_Unmarshal_MapStrInt/codec=json/n=25
   gendemo.BenchmarkSpec_Unmarshal_MapStrInt/codec=cbor/n=3
   gendemo.BenchmarkSpec_Unmarshal_MapStrInt/codec=cbor/n=25

The general pattern being:

  {nodeImplementation}.BenchmarkSpec_{Application}_{FixtureCohort}/codec={codec}/size={size}

Some variations like "codec=" will only exist for some applications,
e.g. it does exist for marshal and unmarshal, but of course doesn't
apply for traversal.

In the process, noticed we're using the test subject nodebuilder for
part of the selector setup too... which is... well, it's not wrong,
per se, but it's certainly tangental.  I don't see any good way to
avoid it though, so, there's now just a comment about this fact.

Lots of import cycle fixing was necessary to get here, which was an
unpleasant surprise at the start of the day... but lots of things are
better off now, so it was highly worth it.

This is the last part of the cleanup and cyclic import fix started
in the previous commit.

Previously it was in the 'impl/typed' package, next to the
runtime-wrapper implementation of the interface.  This was strange.

Not only should those two things be separated just on principle,
this was also causing more import cycle problems down the road:
for example, the traversal package needs to consider the *interface*
for a schema-typed node in order to gracefully handle some features...
and if this also brings in a *concrete* dependency on the
runtime-wrapper implementation of typed nodes, not only is that
incorrect bloat, it becomes a show stopper because (currently, at
least) that implementation also in turn transitively imports the
ipldfree package for some of its scalars.  Ouchouch.

So.  Now the interface lives over in the 'schema' package, with all
the other interfaces for that feature set.  Where it probably always
should have been.

('typed.Maybe' also became known as 'schema.Maybe', which... does not
roll off the tongue as nicely.  But this is a minor concern and we
might reconsider the naming and appearance of that thing later anyway.)

traversal.NodeBuilderChooser can now return error.  Also, the default no longer returns ipldfree.NodeBuilder.

The traversal package having a dependency on the ipldfree Node
implementation package was problematic: it's important that we be able
to benchmark traversal *in combination* with different implementations
of Node, and it turns out if we want to build reusable test and
benchmark functions for that, we get cyclic dependencies when then
trying to use them on our most common implementation!  Ouch.

Having a default implementation of Node referenced was originally out
of a desire for convenience.  But it's logically dubious anyway.
Even the convenience gain in practice is questionable since one still
always needs to configure a LinkLoader in the same areas.  At any rate,
hopefully the error message is helpful enough to make this low-impact.

(We could probably benefit from more helper methods around this, too.
But we can review that later.  Preferably after the 'NodeStyle' feature
from the R&D branches lands, also, which should make this whole area
better named, clearer about where its allocations arrive, and just
less fidgety in general.)

Getting *enough* and sufficiently *organized* corpuses becomes a
legitimate challenge.

The docs outline some of the directions this will go while describing
the naming convention.

This naming convention has already been cropping up in an ad-hoc way in
recent commits; this is a step towards documenting it consistently.

There aren't many entries yet; expect it to grow.

Using JSON as the defacto format is a little aggressive, perhaps,
because it makes sort of a wide dependency span.
But since we've already long had unmarshalling of json working,
it seems viable in practice.
And it means we get the marshalling output target corpuses for free
for at least one of our formats.
And it means we can readily make comparisons to stdlib json,
which is nice for having baselines to frame comparisons against.
It also has the interesting sideeffect of making these corpuses
immune to change in the face of refactors to NodeBuilder (which
will be an absurd concern at any time except... right now).
(We'll see.  Maybe I'll regret this after some time passes.  But if so,
this content probably just pivots to being still useful in json
marshal and unmarshal tests.)

I'd like to put this to work in writing more traversal benchmarks...
but that's going to have to wait a few commits, because I've found some
import cycles that get very problematic when I try to proceed there,
and it looks like they might take a few steps to sort out.

Path clarifications

Previous commit with suggestions from reviewer made me look at this
line again and realize it was *too* specific.

There's already explicit sections for empty string and slash cases,
on the basis of how likely those are to provoke questions
(even though the content is essentially to highlight how *not*
exceptional they are); it makes just as much sense to do the same
call out for null bytes.

Original text started in
https://github.com/ipld/go-ipld-prime/pull/47/files#r384127483 .
Co-Authored-By: Peter Rabbitson <ribasushi@leporine.io>

Yep, it makes a lot of creation by struct uglier, as you can see in the
diff to the test file.  Fortunately?  Nobody outside the package is
allowed to do that anyway, so, we can pretty much ignore the ergonomic.
(It'll still look uglier if someone's looking at stuff with spew or
go-cmp or some other library like that which peeks naughtily into
unexported fields, but that's hard to do much about.)

We could also address this by adding a discriminant field to the
PathSegment struct.  (If we wanted to use uint internally, we'd
probably have to do that, in fact.  Either that or start using
some other alarmingly magical number like UINT_MAX.  Ygh.)  I didn't.
I don't think we handle lists larger than 2 billion elements
particularly well anyway... so, adding more words of memory to
PathSegment to support that case seems like an entirely losing trade.

This one takes 489ns/op... indicating that indeed 54.6% of the time
spent by the real marshalling of json is on the json details.

I would've thought this would be even larger, actually.  Hm.

May keep this 'null' marshaller.  Not sure.  Does it tell a useful
story, or tell a story clearer than doing the same thing with json?
Signed-off-by: Eric Myhre <hash@exultant.us>

Porting codecs to the new NodeAssembler interfaces was straightforward.

The new codecs exist in the nodesolution "research" dirs for now,
coexisting with the soon-to-be-legacy encoding package.
This means we can see benchmarks of both the old and new designs within
this commit.  (We'll probably give up on this shortly -- when dealing
with the traversal package too, it's gonna stop being reasonable -- but
for now it's still possible and provides interesting information.)

And how *is* that performance, you ask?

Peachy.

Ballpark answers for marshalling:

- 1079ns/op for the new Node
- 1435ns/op for the old Node
- 1559ns/op for stdlib json marshal of a native map.

144% better than the operations of stdlib json is pretty acceptable.
(Will more intense codegen beat that?  Oh for sure.  But this is
*without any codegen*, so this is quite satisfactory.)

Note that much of that time left is probably dominated by
serialization-related allocations rather than the node traversal.
I didn't dive into the pprofs to verify that yet, though.
This picture of the overall act of marshalling is nice to have
since it's a practical end-to-end user story.

This test is also on a very small piece of data, and I expect
the improvements will be further much bigger on larger or
deeper-recursing structures.

And lest this be skimmed over: the excellence of doing better than
stdlib's json **while having pluginable codecs** cannot be understated.

Pretty happy with this.

How's unmarshal?  Eh.  About the same as before.  Remember, we chose
*not* to do a lot of amortizations in the new 'basicnode'
implementations, because although we *could* (and it's quite clear how
to do so), the increase in memory size we'd face since go doesn't allow
unions was deemed too large of a constant factor multiplier.
We *will* see these improvements in codegen, and we can also make
variants of 'basicnode' that do these amortizations in the future.

Doing a lot of thinking about how benchmarks and tests will be managed
as they continue to grow in count and in variation of semantic targets.
Might have to write some tooling around it.  We'll see.

The '_rsrch/nodesolution' package is almost ready to replace the
current core go-ipld-prime interfaces,
and the '_rsrch/nodesolution/node/basic' corresondingly replace
the current 'impl/free' package.

This first crossed my mind when considering whether it might be a good
idea to export the concrete implementation types of the 'basicnode'
package (see previous couple of commits -- it mostly had to do with the
question of whether we could reuse more code and shrink the size of
packages emitted by codegen)... but even though that's resolved to a
pretty solid "nope", it still makes sense to have a consistent name
prefix pattern here... and we'll probably encourage and expect to see
similar conventions in other packages (including in codegen, if we
add a handy-constructor-funcs feature to that).

And with this, the gendemo package both compiles and passes tests
once again.  yay!  Onward!

Check out the 'HACKME_scalars.md' file for why this commit represents
a bunch of nontrivial decisions.  There are a lot of possible ways
the compile failures here could be fixed, but some of them would have
bigger consequences of longterm weirdness than others.

Or at least, it certainly looks that way from here.  Maybe we'll see.

The scalar implementations are almost exact replicates of the basicnode
implementations.  Oddly, they haven't been exported yet.  This may
change (again, see discussion in the HACKME_scalars document) -- in
which case the code will also change to use wrapper structs.
Note one other divergence: the error messages have different content
for the typename: we mention the package, since this will probably be
typical and useful for codegen-created types in general.

The gendemo package almost compiles again.  The rest of the fixes
aren't related to this topic, so come in the next commit.

I... honestly hadn't even realized this before; I just noticed it
when making a refactor that would produce this end state, and thought
"oh, that's silly".  Evidently... it's fine, since this has already
been the case, and not been problematic!  Alright then.
Apparently it's not too silly after all.

It's not very often we care about these things in Go, and when we do,
this stance of "string is really just bytes; guard it yourself" is
the community norm... so, these docs should *almost* go without saying.
However, since IPLD is all about cross-language consistency, and
we may have people from other programming language ecosystems reading
our docs, it seems good to be as clear and explicit as possible.

Primarily, being commital and direct about how special values, erm...
*aren't* -- namely, "/" is a valid segment, and so is empty string --
and confessing how much tricky work that makes.

Several methods are now more upfront about how much they *do not do
good things* on such values.

Added some new constructors for Path which *do* work for all possible
values.  (You could've handled such tricky values with a series of
Join calls, previously, but that would be ergonomically grueling.)

These facts are all defacto 'true' to the best of my knowledge now.
However, the IPLD specs repo is a bit on the quiet side about them
at present (precisely because it's such an irritating little nest of
edge cases and fun stuff)... and so the comments are also littered
with "this may change" warnings.  Still, it's better to be accurate
about what the code does and does not do in its current state.

I'd *like* to formally specify an escaping system and canonical
string encoding for paths.  That should start in the IPLD Specs
repo, though, and involve fixtures, so I won't start it here now.

Thanks to @ribasushi for the kick in the shins that these docs needed
work and clarifications.

Turns out there was a lot of tech debt already accumulating very very
rapidly due to the earlier whimiscal choice to lump the new basicnode
implementations and the demo-codegen implementations into the same
packages as benchmarking and research on this branch began.

The basicnode package is now extracted cleanly, and exists in the
'node/basic' path.  This 'basicnode' package is the equivalent of what
was formerly called 'ipldfree' on the master branch.

The demo codegen content is now under 'node/gendemo'.
Note that it is BROKEN in this commit; there was too much there to
clean up and address in one commit, and this one has already become
quite large and includes a bewildering number of moves as well as
finer content rearrangements.  Fixes will come in next commit(s).

(Why?  Well, the demo codegen content leaned on the basicnode types
for string and int.  Turns out this actually opens *quite* the
can of worms when you try to rectify it.
At the surface level, the basicnode package's types aren't exported.
Could we export them?  Well, sure.  Except that's only half the trick.
Can we export the *assemblers* for those types?  Well, sure.  But...
Can we export the 'w' fields for those assemblers for those types?
**NO** -- this is where it all breaks down -- if those fields are
exported, we lose all control over all immutability everywhere.
Shoot...?  Very shoot.
One clearly correct solution to this is to generate new types for
all of the primitive scalars in every codegen output package;
the downside, obviously, is that's a bit verbose in resulting code.
There might be another very alexandrian solution to this gordian knot:
exporting the basicnode package's types after all, but not their
assemblers; then leaning further into their implementation detail
of being implemented as typedefs rather than strictly enclosed structs,
and having every part of codegen types that handle primitive leafs
directly perform and manage the relevant casts.  The bigger picture
wisdom of this has not been completely analyzed yet.)

The 'impls' path has in general become 'node'.
This will stay this way when we finally merge over core on master;
all the current 'impl' (without the s; sigh) paths will become 'node'.

Numerous new HACKME files have appeared; some are splits of old ones
to account for the new package splits; some are hoisted and polished
from what were previously commentstorms in the code; some are
completely new.  There are also a few new package-scope godocs.

The benchmarks and tests are rearranged and much (much) improved.
Naming is more consistent; and things are consistently extracted
to the 'node/mixins/tests' package, and imported and used from there.
(If you want all the same benchmark info as before, you'll now have
to run benchmarks from several different packages.)

The last line is still particularly interesting and nonobvious, though.
It's good that the current design does *not* expose memory anywhere
during mid-construction, even to parts that are semi-finalized:
if we did, and it so happened that a backing array had to grow, we'd
end up releasing pointers to several backing arrays into the wild,
which would probably end up rather terrible and rather hard to see.

It's become clear that `map[string]struct{k, v Node}` is the correct
choice in a wide variety of ways; we've already gone all in on that.

The rest of the comment is speculative, and not wrong, but it'll be
just as well to reboot those speculations later, and many of the things
that were in flux when that comment was penned aren't anymore, so a
revisit should be simpler.

This is a rather important detail to remember, and one that is easy to
lose track of if not actively wrangling the schema typed usecases.
(And so, I almost did.  Uufdah.)

The various methods for getting NodeStyle out of assemblers are now
much better documented.

As my current goals are still revolving around finishing the new
'ipldfree'/'basic' nodes, wrapping up this whole research branch,
and bringing these interface back to land in the library core...
I'm still not bothering to substantially handle the inside of the
ValueStyle methods on the example struct types.  But it should be
clear enough how to implement them correctly now.