TONYC TPF Grant 13 report 16

[Hours]         [Activity]
2020/02/24      Monday
 2.05           #17555 re-check
 0.13           #17555 push and ask for help
 0.70           sec #112 review discussion
 0.65           #17568 review and apply to blead
=====
 3.53

2020/02/25      Tuesday
 2.53           #17555 try a different approach, looks good so far
=====
 2.53

2020/02/26      Wednesday
 1.25           #17555 testing and benchmarking, create PR #17583.
 0.88           #17570 review and briefly comment
 0.72           #17564 debugging
 1.50           :utf8 finish stricting, add more invalid encoding support
                and tests
=====
 4.35

2020/02/27      Thursday
 1.12           check Storable format issues informally reported by khw
                (32-bit build only)
 0.42           #17541 research and briefly comment
 0.47           review travis failure, turned out to be unrelated to my
                commit, irc discussion
 0.63           :utf8 debugging
=====
 2.64

Which I calculate is 13.05 hours.

Approximately 6 tickets were reviewed or worked on, and 1 patches
were applied.

Among other things, I found a working solution for #17555 this week.

My original attempt used a linked list of linked lists:

  headslab.opslab_freed
    |
    V
  head op of size N  (op_next)-> more freed ops of size N
    | (op_sibparent)
    V
  head op of size N+M (op_next)-> more freed ops of size N+M
   ...

which broke the build.

The eventual solution changed opslab_freed from being an OP* pointing
at the first freed op to an OP** pointing at an array of linked lists,
and added an opslab_freed_size which is the size of that array.

  head_slab.opslab_freed->
    [0] ops same size as BASEOP (op_next)-> more freed ops same size as BASEOP
    [1] ops size of BASEOP+1 (in pointer units)
    ...
    [i] NULL (no ops of this size)
    ...
    [opslab_freed_size-1] ...

This has the advantage that addition to the freed ops "list" is now
amortized O(1) assuming that op sizes don't have a huge range.

Finding a freed op isn't quite O(1) (vs previously being O(number of
freed ops)), since a given size might not have any freed ops, in which
case the array is searched for larger sizes, but it's much closer than
before.

This also ended up fixing #17586 which observed that populating hashes
with many separate statements had slowed since 5.18.

• TONYC TPF Grant 13 report 16 by Tony Cook