Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: google/btree
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: v1.0.1
Choose a base ref
...
head repository: google/btree
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: v1.1.3
Choose a head ref
  • 11 commits
  • 8 files changed
  • 6 contributors

Commits on Aug 30, 2021

  1. Switch to github actions

    Matt Gaunt committed Aug 30, 2021
    Configuration menu
    Copy the full SHA
    297f399 View commit details
    Browse the repository at this point in the history
  2. Add verbose flag

    Matt Gaunt committed Aug 30, 2021
    Configuration menu
    Copy the full SHA
    cc35b3d View commit details
    Browse the repository at this point in the history
  3. Remove travis badge

    Matt Gaunt committed Aug 30, 2021
    Configuration menu
    Copy the full SHA
    b5a6bf7 View commit details
    Browse the repository at this point in the history
  4. Merge pull request #39 from google/actions

    Switch to github actions
    gauntface authored Aug 30, 2021
    Configuration menu
    Copy the full SHA
    ac7cc57 View commit details
    Browse the repository at this point in the history

Commits on Jun 4, 2022

  1. Create a generic BTreeG for Go 1.18 and beyond.

    With the introduction of generics in Go 1.18, we have the opportunity
    to use them for our btrees.  However, we want to make sure that our API
    remains compatible with past uses.  So, we introduce a new BTreeG which
    is a generic API.  We then utilize it to recreate the original BTree
    of Item interfaces.
    
    Go compilers <1.18 will compile btree.go, containing just the original
    BTree of Items.  Go compilers >=1.18 instead compile btree_generic.go
    which creates the BTreeG generic and uses it to make a BTree of Items
    with the same API as that exposed in btree.go.
    
    One major difference between the APIs of BTree and BTreeG is that, for
    BTree, we could return a `nil` Item to connote "nothing was found".  For
    generics, users may often want to store the zero value, so we can't
    treat the zero value as "missing".  For that reason, you'll see these
    differences in APIs:
    
    ```
      func (t *Btree)     Get(item Item) Item      { ... }
      func (t *BtreeG[T]) Get(item T)    (T, bool) { ... }
    ```
    
    Note that we now return a second boolean return value, which is true
    if the value was found and false otherwise.
    
    Using the generic for base types like `int` greatly speeds up processing,
    since it removes the need for the `Item` interface to be
    created/malloc'd, and it allows more contiguous storage of values within
    the BTree's nodes themselves.
    
    As expected, all G (generic) ops are notably faster than their associated
    Int Item ops, because of the removal of interface overhead.  Untested here,
    but they should also be far less memory-fragmented, since values are
    stored within the node item arrays rather than pointed to by interfaces
    within those arrays.
    
    BenchmarkInsertG-4                      	 	 3014830	     355.2 ns/op
    BenchmarkInsert-4                       	 	 2296561	     639.9 ns/op
    
    BenchmarkSeekG-4                        	 	 5478997	     218.6 ns/op
    BenchmarkSeek-4                         	 	 2880756	     396.0 ns/op
    
    BenchmarkDeleteInsertG-4                	 	 1720306	     653.0 ns/op
    BenchmarkDeleteInsert-4                 	 	 1304244	      1131 ns/op
    
    BenchmarkDeleteInsertCloneOnceG-4       	 	 1834026	     647.3 ns/op
    BenchmarkDeleteInsertCloneOnce-4        	 	 1293346	     932.3 ns/op
    
    BenchmarkDeleteInsertCloneEachTimeG-4   	 	  545394	      2878 ns/op
    BenchmarkDeleteInsertCloneEachTime-4    	 	  353428	      4173 ns/op
    
    BenchmarkDeleteG-4                      	 	 3223182	     366.9 ns/op
    BenchmarkDelete-4                       	 	 1979107	     600.4 ns/op
    
    BenchmarkGetG-4                         	 	 4265853	     293.2 ns/op
    BenchmarkGet-4                          	 	 3091616	     431.8 ns/op
    
    BenchmarkGetCloneEachTimeG-4            	 	 1990131	     693.3 ns/op
    BenchmarkGetCloneEachTime-4             	 	 1705196	     610.0 ns/op
    
    BenchmarkAscendG-4                      	 	   14222	     83445 ns/op
    BenchmarkAscend-4                       	 	   12345	     94486 ns/op
    
    BenchmarkDescendG-4                     	 	   14335	     80779 ns/op
    BenchmarkDescend-4                      	 	   11686	     98627 ns/op
    
    BenchmarkAscendRangeG-4                 	 	    8803	    134915 ns/op
    BenchmarkAscendRange-4                  	 	    5586	    209962 ns/op
    
    BenchmarkDescendRangeG-4                	 	    6590	    182179 ns/op
    BenchmarkDescendRange-4                 	 	    3591	    323628 ns/op
    
    BenchmarkAscendGreaterOrEqualG-4        	 	   12984	     92049 ns/op
    BenchmarkAscendGreaterOrEqual-4         	 	    9915	    121264 ns/op
    
    BenchmarkDescendLessOrEqualG-4          	 	    7876	    152083 ns/op
    BenchmarkDescendLessOrEqual-4           	 	    4945	    231001 ns/op
    
    BenchmarkDeleteAndRestoreG/CopyBigFreeList-4         	     100	  10167381 ns/op	   75390 B/op	      15 allocs/op
    BenchmarkDeleteAndRestore/CopyBigFreeList-4          	      73	  15137467 ns/op	  141924 B/op	      19 allocs/op
    
    BenchmarkDeleteAndRestoreG/Copy-4                    	     104	  12522643 ns/op	  235632 B/op	    1195 allocs/op
    BenchmarkDeleteAndRestore/Copy-4                     	      80	  16853292 ns/op	  433896 B/op	    1151 allocs/op
    
    BenchmarkDeleteAndRestoreG/ClearBigFreelist-4        	     207	   5434805 ns/op	     670 B/op	       4 allocs/op
    BenchmarkDeleteAndRestore/ClearBigFreelist-4         	     147	   7954534 ns/op	     980 B/op	       6 allocs/op
    
    BenchmarkDeleteAndRestoreG/Clear-4                   	     198	   6781077 ns/op	  148424 B/op	    1086 allocs/op
    BenchmarkDeleteAndRestore/Clear-4                    	     134	   8639437 ns/op	  268872 B/op	    1041 allocs/op
    gconnell committed Jun 4, 2022
    Configuration menu
    Copy the full SHA
    1257d40 View commit details
    Browse the repository at this point in the history
  2. Configuration menu
    Copy the full SHA
    be61f00 View commit details
    Browse the repository at this point in the history
  3. Use ~string for Ordered.

    gconnell committed Jun 4, 2022
    Configuration menu
    Copy the full SHA
    770c3d8 View commit details
    Browse the repository at this point in the history

Commits on Jun 7, 2022

  1. ci: use github actions matrix

    Signed-off-by: Tuan Anh Tran <[email protected]>
    tuananh authored and gconnell committed Jun 7, 2022
    Configuration menu
    Copy the full SHA
    e5eabf3 View commit details
    Browse the repository at this point in the history

Commits on Jun 15, 2022

  1. Configuration menu
    Copy the full SHA
    3f48535 View commit details
    Browse the repository at this point in the history
  2. Add coverage of Has in test.

    gconnell committed Jun 15, 2022
    Configuration menu
    Copy the full SHA
    8e29150 View commit details
    Browse the repository at this point in the history

Commits on Aug 21, 2024

  1. fix: remove item may changed clone btree; (i+1) children has new cow,…

    … but do not copy
    
    Signed-off-by: zhangchuanqing1 <[email protected]>
    zhangchuanqing5658 authored and gconnell committed Aug 21, 2024
    Configuration menu
    Copy the full SHA
    aeba20f View commit details
    Browse the repository at this point in the history
Loading