Binary Search Optimizations

[jamescourtney]

Optimize memory allocations during binary search:

• No more delegate allocations (structs instead!)
• In non-greedy modes, add a fast-path binary search that avoids the byte -> string -> byte indirection that is necessary if going through the deserialized type.
• Make use of ArrayPool<byte>.Shared to avoid allocating temporary buffers

Results:

original
|           Method |        Option | Length | TravCount |     Mean |     Error |    StdDev |     Gen 0 |    Gen 1 |    Allocated |
|----------------- |-------------- |------- |---------- |---------:|----------:|----------:|----------:|---------:|-------------:|
|        Serialize |          Lazy |  10000 |         1 | 1.603 ms | 0.0226 ms | 0.0269 ms |         - |        - |         90 B |
| ParseAndTraverse |          Lazy |  10000 |         1 | 8.921 ms | 0.2489 ms | 0.2963 ms | 1328.1250 |        - | 22,442,928 B |
|        Serialize | GreedyMutable |  10000 |         1 | 1.585 ms | 0.0167 ms | 0.0199 ms |         - |        - |         90 B |
| ParseAndTraverse | GreedyMutable |  10000 |         1 | 4.736 ms | 0.0955 ms | 0.1137 ms |  296.8750 | 125.0000 |  5,040,144 B |

with fixes
|           Method |        Option | Length | TravCount |     Mean |     Error |    StdDev |   Gen 0 |   Gen 1 |   Allocated |
|----------------- |-------------- |------- |---------- |---------:|----------:|----------:|--------:|--------:|------------:|
|        Serialize |          Lazy |  10000 |         1 | 1.459 ms | 0.0154 ms | 0.0040 ms |       - |       - |        90 B |
| ParseAndTraverse |          Lazy |  10000 |         1 | 3.967 ms | 0.1170 ms | 0.0181 ms | 39.0625 |       - |   720,107 B |
|        Serialize | GreedyMutable |  10000 |         1 | 1.377 ms | 0.0014 ms | 0.0004 ms |       - |       - |        90 B |
| ParseAndTraverse | GreedyMutable |  10000 |         1 | 4.849 ms | 0.0348 ms | 0.0054 ms | 78.1250 | 31.2500 | 1,360,147 B |

[codecov[bot]]

Codecov Report

Merging #261 (6b7fe5c) into main (d624e91) will increase coverage by 0.20%. The diff coverage is 98.56%.

@@            Coverage Diff             @@
##             main     #261      +/-   ##
==========================================
+ Coverage   95.25%   95.46%   +0.20%     
==========================================
  Files         109      109              
  Lines        7168     7275     +107     
  Branches      673      681       +8     
==========================================
+ Hits         6828     6945     +117     
+ Misses        237      230       -7     
+ Partials      103      100       -3     

Impacted Files	Coverage Δ
src/FlatSharp.Runtime/SortedVectorHelpers.cs	97.65% <98.14%> (+4.49%)	:arrow_up:
src/FlatSharp.Runtime/StringSpanComparer.cs	100.00% <100.00%> (ø)
...arp.Runtime/Vectors/FlatBufferProgressiveVector.cs	94.11% <100.00%> (+0.24%)	:arrow_up:
src/FlatSharp.Runtime/Vectors/FlatBufferVector.cs	96.66% <100.00%> (+1.01%)	:arrow_up:
.../FlatSharp.Runtime/Vectors/FlatBufferVectorBase.cs	93.68% <100.00%> (+0.20%)	:arrow_up:
src/FlatSharp.Runtime/Vectors/IndexedVector.cs	100.00% <100.00%> (ø)
...tSharp/Serialization/DeserializeClassDefinition.cs	100.00% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update d624e91...6b7fe5c. Read the comment docs.