minor optimization

[glycerine]

1. btree.go line 152 should be index < len(*s) - 1, because otherwise the "if" is always true,
   and the minor optimization of not calling a copy that is going to do nothing anyway (as [index+1:] gives an empty slice when index==len(*s)-1 so copy into an empty slice does nothing anyway) is missed... right? (edit: or omit the if? profiling might show the cpu is happier with straight-line rather than branching code...)

func (s *items) insertAt(index int, item Item) {
    *s = append(*s, nil)
    if index < len(*s) { // line 152
        copy((*s)[index+1:], (*s)[index:])
    }
    (*s)[index] = item
}

2. On sequential reads (a "full table scan") this b-tree kicks some serious butt.
   It is sooo fast. And inserts are fantastically fast too. I mean, a full in-order read so
   much faster than the built-in go map it is like 2x ridiculous--probably due to way fewer
   cache misses. But the thing is, deletes are suuuper slow in comparison. Do you
   have any intuition as to why deletes from the btree are so slow? Could tombstoning help?
   I saw the comments on Clear but I want to support arbitrary delete patterns
   and not have them be so very different from insert.

Comparison to built in Go map:

map time to store 10_000_000 keys: 2.466118634s (246ns/op)                                     
map reads 10_000_000 keys: elapsed 101.076718ms (10ns/op)                                      
map deletes 10000000 keys: elapsed 1.36421433s (136ns/op)   

// degree 30 b-tree github.com/google/btree (and 3000 even faster)                             
google/btree time to store 10_000_000 keys: 1.835054285s (183ns/op)                              
google/btree reads 10_000_000 keys: elapsed 52.309863ms (5ns/op)                                 
// (deletes are very slow though! like an order of magnitude slower...)
google/btree delete 10_000_000 keys: elapsed 13.386230659s (1.338µs/op)  

[glycerine]

Ah. On the question 2 about slow deletes, I figured out this was due to my tuning, not anything intrinsic to this library.

Details if anyone is concerned:

(code is available here: https://github.com/glycerine/uart/tree/bench_goog_btree )

I had tuned the btree for load and read performance, not realizing the impact this would have on delete performance, for which I added measurements much later. The fastest load and read I observed was with a large degree, degree 3000 specifically. When comparing degree 3000 to degree 32, the benchmark code linked above shows:

The degree 3000 is 30% faster to load, 60% faster on sequential read, BUT 6x slower on delete, compared to a degree 32 btree.

So it is simply a matter of balancing for your use case. If you do no deletes, and want the fastest full table scans, use a very large degree (say 3000 degree) btree. If you do frequent deletes, then use a more modest (say 32 degree) btree, which will be somewhat slower to load and read (30% - 60%), but not be inordinately slow on delete.

    // degree := 3_000 // fastest load/read                                                    
    // google/btree time to store 10000000 keys: 1.404165436s (140ns/op)                       
    // google/btree read all keys: elapsed 28.916136ms (2ns/op)                                                                                    
    // google/btree delete all keys: elapsed 13.549681183s (1.354µs/op)      

    degree := 32 // slower load/read, but MUCH faster delete.                                  
    // google/btree time to store 10000000 keys: 2.097327599s (209ns/op)                       
    // google/btree read all keys: elapsed 49.415972ms (4ns/op)                                                                                    
    // google/btree delete all keys: elapsed 2.024685985s (202ns/op)