Hex encoding can be significantly faster

[Kixunil]

I figured if we encode into a temporary array first and then call a single write_str the performance improves quite a lot.
With reasonably simple unsafe we can squeeze out a bit better performance on top of that.

Relevant benchmarks - encoding 32B:

test tests::thirtytwo::trivial::sink        ... bench:       1,577 ns/iter (+/- 567)
test tests::thirtytwo::trivial::string      ... bench:       1,882 ns/iter (+/- 194)
test tests::thirtytwo::with_buf::sink       ... bench:          57 ns/iter (+/- 29)
test tests::thirtytwo::with_buf::string     ... bench:          92 ns/iter (+/- 3)
test tests::thirtytwo::with_unsafe::sink    ... bench:          47 ns/iter (+/- 21)
test tests::thirtytwo::with_unsafe::string  ... bench:          92 ns/iter (+/- 12)
test tests::thirtytwo::maybe_uninit::sink   ... bench:          43 ns/iter (+/- 6)
test tests::thirtytwo::maybe_uninit::string ... bench:          79 ns/iter (+/- 40)

trivial is the current impl, with_buf uses temporary buffer without unsafe, with_unsafe uses unsafe only to call from_utf8_unchecked, maybe_uninit also uses uninit buffer. (IOW "more unsafe")

sink only passes the buffer into black box, while string calls to_string(). The performance difference is larger here because a single write avoids reallocation.

Full bench code with other benchmarks

I intend to submit a PR with this together with other refactors mentioned earlier, my question is if I should use unsafe or not.

[apoelstra]

whoah.

I'm gonna say "no" on "unsafe" for now, because the performance benefit is relatively small and it'd represent something of a policy change for the project.

[Kixunil]

What's the policy on unsafe here? I just found some unsafe spanning over two pretty long functions in siphash24 and it looks like it's unsafe only for perf reasons and I suspect it could be made safe with a bit of though. (I still don't understand the code well enough to say for sure.) AFAIK checked accesses are super-fast on computers from this century thanks to branch predictions, so I'd guess the perf benefit may be even smaller than what I suggested.

My suggested unsafe is very clear compared to what I found IMO (or at least from_utf8_unchecked is).

Not pushing hard for my unsafe, just for consistency and trying to understand things better.

[Kixunil]

Oh, it's even worse, it calls a macro that does some bespoke stuff and is definitely wrong (even if not unsound) because it's called _le but what it actually does is _ne. So siphash24 should break on big-endian architectures.

I believe that chunk of unsafe can be removed completely. The compiler is already smart to optimize that. Also it looks like iterators could be used in u8_to64_le instead of index which might fix the perf issues.

[elichai]

FWIW docs.rs/faster-hex/ Is pretty cool and extremely fast

[Kixunil]

And pretty undocumented...

[apoelstra]

@Kixunil the unsafety in siphash24 is in bitcoin_hashes which is a simpler and lower-turnover crate. Wherease in rust-bitcoin we have forbid(unsafe) and I'd like to keep that.

Having said this, the unsafety in bitcoin_hashes is pretty eyebrow-raising. As you say, the code appears to be incorrect; it received almost no review (it originated in #46 ) although I do believe I checked the unsafety for soundness issues; and it also represents the only unsafety in that library except in Matt's constant-time comparison function (which is much simpler and easier to vet). Also the comments suggest that we ripped the code from siphasher in violation of its license, which we should fix ASAP.

[Kixunil]

I was suggesting putting it into bitcoin_hashes (although maybe we should have it in internals crate later).

in rust-bitcoin we have forbid(unsafe) and I'd like to keep that.

So no unsized Script? Or should script be a separate crate so that forbid stays?

[apoelstra]

So no unsized Script? Or should script be a separate crate so that forbid stays?

We should probably open a discussion rather than talking here -- but I would like to have unsized script :) so I guess we need a more nuanced policy than "forbid stays and covers the whole crate".

[Kixunil]

Opened rust-bitcoin/rust-bitcoin#1228

[apoelstra]

Closing in favor of rust bitcoin 1261.