remove a mis-optimization that hurt performance for uneven updates

If the total number of chunks hashed so far is e.g. 1, and update() is
called with e.g. 8 more chunks, we can't compress all 8 together. We
have to break the input up, to make sure that that 1 lone chunk CV gets
merged with its proper sibling, and that in general the correct layout
of the tree is preserved. What we should do is hash 1-2-4-1 chunks of
input, using increasing powers of 2 (with some cleanup at the end). What
we were doing was 2-2-2-2 chunks. This was the result of a mistaken
optimization that got us stuck with an always-odd number of chunks so
far.

Fixes https://github.com/BLAKE3-team/BLAKE3/issues/69.

1 files changed, 19 insertions, 0 deletions

diff --git a/benches/bench.rs b/benches/bench.rs
index 70be967..263f81e 100644
--- a/benches/bench.rs
+++ b/benches/bench.rs
@@ -475,3 +475,22 @@ fn bench_rayon_0512_kib(b: &mut Bencher) {
 fn bench_rayon_1024_kib(b: &mut Bencher) {
     bench_rayon(b, 1024 * KIB);
 }
+
+// This checks that update() splits up its input in increasing powers of 2, so
+// that it can recover a high degree of parallelism when the number of bytes
+// hashed so far is uneven. The performance of this benchmark should be
+// reasonably close to bench_incremental_0064_kib, within 80% or so. When we
+// had a bug in this logic (https://github.com/BLAKE3-team/BLAKE3/issues/69),
+// performance was less than half.
+#[bench]
+fn bench_two_updates(b: &mut Bencher) {
+    let len = 65536;
+    let mut input = RandomInput::new(b, len);
+    b.iter(|| {
+        let mut hasher = blake3::Hasher::new();
+        let input = input.get();
+        hasher.update(&input[..1]);
+        hasher.update(&input[1..]);
+        hasher.finalize()
+    });
+}