util/interval/generic: stop lying about live memory by ajwerner · Pull Request #116663 · cockroachdb/cockroach

ajwerner · 2023-12-18T15:25:30Z

See individual commits. The basic problem this PR solves is that in the previous formulation, we used unsafe code to cast pointers to nodes to point beyond their allocation. It's not clear that this is sound with regards to GC, and it's certain that this break tools like viewcore. The argument for this hack was performance. This change removes unsafe code and achieves effectively the same performance.

name                                                       old time/op    new time/op    delta                                                                                                                                                                                   
BTreeInsert/count=128-32                                     47.9ns ± 1%    46.5ns ± 6%  -2.80%  (p=0.000 n=8+20)                                                                                                                                                                
BTreeInsert/count=1024-32                                    61.5ns ± 2%    60.3ns ± 3%  -2.10%  (p=0.000 n=10+20)                      
BTreeInsert/count=8192-32                                     128ns ± 1%     129ns ± 2%    ~     (p=0.107 n=9+20)                       
BTreeInsert/count=65536-32                                    196ns ± 1%     199ns ± 3%  +1.87%  (p=0.000 n=10+20)                      
BTreeDelete/count=128-32                                     52.1ns ± 8%    54.6ns ±13%  +4.96%  (p=0.022 n=10+20)                      
BTreeDelete/count=1024-32                                    92.1ns ± 9%    91.4ns ±11%    ~     (p=0.657 n=10+20)                      
BTreeDelete/count=8192-32                                     168ns ± 3%     166ns ± 4%    ~     (p=0.211 n=9+20)                       
BTreeDelete/count=65536-32                                    255ns ± 2%     258ns ± 3%    ~     (p=0.080 n=10+20)                      
BTreeDeleteInsert/count=128-32                               87.2ns ± 3%    86.5ns ± 3%    ~     (p=0.286 n=10+19)                      
BTreeDeleteInsert/count=1024-32                               205ns ± 3%     204ns ± 5%    ~     (p=0.823 n=8+20)                       
BTreeDeleteInsert/count=8192-32                               245ns ± 3%     247ns ± 4%    ~     (p=0.379 n=10+20)                      
BTreeDeleteInsert/count=65536-32                              416ns ±29%     411ns ±22%    ~     (p=0.729 n=9+20)                       
BTreeDeleteInsertCloneOnce/count=128-32                      88.5ns ± 5%    87.2ns ± 4%    ~     (p=0.091 n=10+20)                      
BTreeDeleteInsertCloneOnce/count=1024-32                      212ns ± 2%     207ns ± 5%  -2.31%  (p=0.007 n=8+17)                       
BTreeDeleteInsertCloneOnce/count=8192-32                      247ns ± 1%     250ns ± 4%    ~     (p=0.120 n=8+20)                       
BTreeDeleteInsertCloneOnce/count=65536-32                     432ns ±19%     415ns ±30%    ~     (p=0.373 n=10+20)                      
BTreeDeleteInsertCloneEachTime/count=128/reset=false-32       527ns ± 5%     531ns ± 6%    ~     (p=0.443 n=10+20)                      
BTreeDeleteInsertCloneEachTime/count=128/reset=true-32        141ns ± 7%     147ns ± 5%  +4.36%  (p=0.001 n=10+20)                      
BTreeDeleteInsertCloneEachTime/count=1024/reset=false-32      951ns ± 3%     965ns ± 3%    ~     (p=0.051 n=9+20)                       
BTreeDeleteInsertCloneEachTime/count=1024/reset=true-32       360ns ± 2%     370ns ± 6%  +2.89%  (p=0.011 n=9+20)                       
BTreeDeleteInsertCloneEachTime/count=8192/reset=false-32     1.04µs ± 1%    1.06µs ± 2%  +1.48%  (p=0.000 n=10+19)                      
BTreeDeleteInsertCloneEachTime/count=8192/reset=true-32       441ns ± 2%     463ns ± 3%  +5.00%  (p=0.000 n=10+20)                      
BTreeDeleteInsertCloneEachTime/count=65536/reset=false-32    1.59µs ±15%    1.52µs ±24%    ~     (p=0.220 n=9+20)                       
BTreeDeleteInsertCloneEachTime/count=65536/reset=true-32      725ns ±15%     789ns ±37%    ~     (p=0.214 n=10+20)                      
BTreeIterSeekGE/count=128-32                                 58.7ns ± 3%    59.5ns ± 5%    ~     (p=0.165 n=10+20)                      
BTreeIterSeekGE/count=1024-32                                89.5ns ± 3%    90.1ns ± 2%    ~     (p=0.373 n=10+20)                      
BTreeIterSeekGE/count=8192-32                                 128ns ± 3%     128ns ± 2%    ~     (p=0.878 n=10+18)                      
BTreeIterSeekGE/count=65536-32                                213ns ± 4%     216ns ± 4%    ~     (p=0.133 n=10+20)                      
BTreeIterSeekLT/count=128-32                                 59.5ns ± 2%    60.9ns ± 3%  +2.22%  (p=0.008 n=10+20)                      
BTreeIterSeekLT/count=1024-32                                92.0ns ± 1%    93.5ns ± 4%  +1.71%  (p=0.006 n=10+20)                      
BTreeIterSeekLT/count=8192-32                                 133ns ± 3%     134ns ± 3%    ~     (p=0.117 n=10+20)                      
BTreeIterSeekLT/count=65536-32                                220ns ± 4%     218ns ± 7%    ~     (p=0.378 n=10+20)                      
BTreeIterFirstOverlap/count=128-32                            170ns ± 3%     170ns ± 3%    ~     (p=0.441 n=10+20)                      
BTreeIterFirstOverlap/count=1024-32                           298ns ± 2%     300ns ± 4%    ~     (p=0.244 n=10+20)                      
BTreeIterFirstOverlap/count=8192-32                           449ns ± 3%     453ns ± 4%    ~     (p=0.403 n=10+20)                      
BTreeIterFirstOverlap/count=65536-32                          590ns ± 4%     584ns ± 3%    ~     (p=0.350 n=10+20)                      
BTreeInsert/count=16-32                                      29.4ns ± 3%    29.1ns ± 3%    ~     (p=0.179 n=10+20)                      
BTreeDelete/count=16-32                                      31.7ns ±16%    32.2ns ±15%    ~     (p=0.447 n=9+10)                       
BTreeDeleteInsert/count=16-32                                52.5ns ± 2%    52.4ns ± 4%    ~     (p=0.796 n=10+10)                      
BTreeDeleteInsertCloneOnce/count=16-32                       52.4ns ± 2%    52.2ns ± 3%    ~     (p=0.436 n=10+10)                      
BTreeDeleteInsertCloneEachTime/count=16/reset=false-32        200ns ± 3%     199ns ± 2%    ~     (p=0.497 n=10+9)                       
BTreeDeleteInsertCloneEachTime/count=16/reset=true-32        68.1ns ± 4%    68.0ns ± 1%    ~     (p=0.965 n=10+8)                       
BTreeIterSeekGE/count=16-32                                  37.9ns ± 4%    38.2ns ± 3%    ~     (p=0.700 n=10+10)                      
BTreeIterSeekLT/count=16-32                                  39.3ns ± 2%    39.6ns ± 3%    ~     (p=0.592 n=10+10)                      
BTreeIterFirstOverlap/count=16-32                             100ns ± 2%     101ns ± 4%    ~     (p=0.271 n=10+10)

name                                           old time/op    new time/op    delta
LockTable/groups=1,outstanding=1,read=0/-32      7.10µs ± 2%    7.08µs ± 2%    ~     (p=0.631 n=10+10)
LockTable/groups=1,outstanding=1,read=1/-32      5.99µs ± 2%    6.09µs ± 2%  +1.56%  (p=0.029 n=10+10)
LockTable/groups=1,outstanding=1,read=2/-32      4.92µs ± 2%    4.94µs ± 2%    ~     (p=0.393 n=10+10)
LockTable/groups=1,outstanding=1,read=3/-32      3.48µs ± 1%    3.54µs ± 2%  +1.79%  (p=0.003 n=10+10)
LockTable/groups=1,outstanding=1,read=4/-32      1.54µs ± 1%    1.56µs ± 1%  +1.07%  (p=0.000 n=10+10)
LockTable/groups=1,outstanding=1,read=5/-32      1.54µs ± 1%    1.56µs ± 1%  +1.15%  (p=0.000 n=10+10)
LockTable/groups=1,outstanding=2,read=0/-32      9.07µs ± 3%    9.15µs ± 1%    ~     (p=0.123 n=10+10)
LockTable/groups=1,outstanding=2,read=1/-32      8.06µs ± 1%    8.09µs ± 2%    ~     (p=0.190 n=10+10)
LockTable/groups=1,outstanding=2,read=2/-32      7.00µs ± 2%    7.09µs ± 1%  +1.24%  (p=0.002 n=10+8)
LockTable/groups=1,outstanding=2,read=3/-32      5.72µs ± 1%    5.77µs ± 4%    ~     (p=0.096 n=8+10)
LockTable/groups=1,outstanding=2,read=4/-32      1.27µs ± 2%    1.29µs ± 2%  +2.09%  (p=0.002 n=10+9)
LockTable/groups=1,outstanding=2,read=5/-32      1.28µs ± 2%    1.29µs ± 2%  +1.21%  (p=0.018 n=9+10)
LockTable/groups=1,outstanding=4,read=0/-32      10.3µs ± 1%    10.3µs ± 1%    ~     (p=1.000 n=10+9)
LockTable/groups=1,outstanding=4,read=1/-32      9.05µs ± 1%    9.11µs ± 2%    ~     (p=0.108 n=10+9)
LockTable/groups=1,outstanding=4,read=2/-32      7.88µs ± 2%    7.96µs ± 1%  +0.98%  (p=0.021 n=10+8)
LockTable/groups=1,outstanding=4,read=3/-32      6.29µs ± 2%    6.39µs ± 1%  +1.66%  (p=0.000 n=9+9)
LockTable/groups=1,outstanding=4,read=4/-32      1.23µs ± 1%    1.24µs ± 2%  +1.06%  (p=0.012 n=10+10)
LockTable/groups=1,outstanding=4,read=5/-32      1.23µs ± 1%    1.25µs ± 1%  +2.22%  (p=0.000 n=10+9)
LockTable/groups=1,outstanding=8,read=0/-32      11.3µs ± 1%    11.4µs ± 4%    ~     (p=0.122 n=8+10)
LockTable/groups=1,outstanding=8,read=1/-32      10.2µs ± 3%    10.2µs ± 1%    ~     (p=0.631 n=10+10)
LockTable/groups=1,outstanding=8,read=2/-32      9.01µs ± 2%    9.17µs ± 1%  +1.81%  (p=0.002 n=10+8)
LockTable/groups=1,outstanding=8,read=3/-32      7.30µs ± 2%    7.39µs ± 2%  +1.21%  (p=0.035 n=10+9)
LockTable/groups=1,outstanding=8,read=4/-32      1.11µs ± 1%    1.12µs ± 1%  +0.90%  (p=0.004 n=10+10)
LockTable/groups=1,outstanding=8,read=5/-32      1.11µs ± 2%    1.13µs ± 3%  +1.86%  (p=0.011 n=10+10)
LockTable/groups=1,outstanding=16,read=0/-32     13.6µs ± 2%    13.5µs ± 3%    ~     (p=0.400 n=9+10)
LockTable/groups=1,outstanding=16,read=1/-32     12.2µs ± 5%    12.1µs ± 5%    ~     (p=0.853 n=10+10)
LockTable/groups=1,outstanding=16,read=2/-32     11.2µs ± 1%    11.0µs ± 6%    ~     (p=0.481 n=10+10)
LockTable/groups=1,outstanding=16,read=3/-32     9.44µs ± 2%    9.50µs ± 2%    ~     (p=0.252 n=10+9)
LockTable/groups=1,outstanding=16,read=4/-32     1.09µs ± 1%    1.10µs ± 1%  +0.89%  (p=0.022 n=10+10)
LockTable/groups=1,outstanding=16,read=5/-32     1.09µs ± 1%    1.10µs ± 1%  +0.83%  (p=0.001 n=10+10)
LockTable/groups=32,outstanding=1,read=0/-32     12.8µs ± 3%    13.0µs ± 0%  +1.26%  (p=0.002 n=9+9)
LockTable/groups=32,outstanding=1,read=1/-32     10.9µs ± 1%    10.8µs ± 3%    ~     (p=0.424 n=10+10)
LockTable/groups=32,outstanding=1,read=2/-32     8.81µs ± 1%    8.93µs ± 1%  +1.32%  (p=0.001 n=10+8)
LockTable/groups=32,outstanding=1,read=3/-32     6.48µs ± 3%    6.52µs ± 1%    ~     (p=0.231 n=9+9)
LockTable/groups=32,outstanding=1,read=4/-32     1.07µs ± 1%    1.07µs ± 0%    ~     (p=0.362 n=10+9)
LockTable/groups=32,outstanding=1,read=5/-32     1.07µs ± 1%    1.08µs ± 1%    ~     (p=0.617 n=10+10)
LockTable/groups=32,outstanding=2,read=0/-32     20.8µs ± 2%    20.8µs ± 3%    ~     (p=0.739 n=10+10)
LockTable/groups=32,outstanding=2,read=1/-32     18.3µs ± 2%    18.3µs ± 2%    ~     (p=0.838 n=10+10)
LockTable/groups=32,outstanding=2,read=2/-32     15.4µs ± 2%    15.7µs ± 2%    ~     (p=0.060 n=10+10)
LockTable/groups=32,outstanding=2,read=3/-32     9.00µs ± 4%    9.11µs ± 2%    ~     (p=0.113 n=10+9)
LockTable/groups=32,outstanding=2,read=4/-32     1.09µs ± 1%    1.09µs ± 1%    ~     (p=0.288 n=10+10)
LockTable/groups=32,outstanding=2,read=5/-32     1.09µs ± 1%    1.09µs ± 1%    ~     (p=0.137 n=10+10)
LockTable/groups=32,outstanding=4,read=0/-32     22.1µs ± 4%    21.7µs ± 2%    ~     (p=0.353 n=10+10)
LockTable/groups=32,outstanding=4,read=1/-32     19.4µs ± 1%    19.4µs ± 3%    ~     (p=0.796 n=10+10)
LockTable/groups=32,outstanding=4,read=2/-32     16.8µs ± 2%    17.0µs ± 3%  +1.05%  (p=0.024 n=9+9)
LockTable/groups=32,outstanding=4,read=3/-32     11.0µs ± 2%    11.1µs ± 1%  +1.01%  (p=0.008 n=9+8)
LockTable/groups=32,outstanding=4,read=4/-32     1.05µs ± 1%    1.04µs ± 1%    ~     (p=0.422 n=10+10)
LockTable/groups=32,outstanding=4,read=5/-32     1.05µs ± 1%    1.05µs ± 1%    ~     (p=0.078 n=10+10)
LockTable/groups=32,outstanding=8,read=0/-32     23.5µs ± 5%    23.4µs ± 4%    ~     (p=0.739 n=10+10)
LockTable/groups=32,outstanding=8,read=1/-32     21.4µs ± 2%    21.6µs ± 3%    ~     (p=0.211 n=9+10)
LockTable/groups=32,outstanding=8,read=2/-32     18.8µs ± 5%    19.3µs ± 1%    ~     (p=0.083 n=10+8)
LockTable/groups=32,outstanding=8,read=3/-32     12.8µs ± 4%    12.9µs ± 1%    ~     (p=0.912 n=10+10)
LockTable/groups=32,outstanding=8,read=4/-32     1.05µs ± 1%    1.05µs ± 1%    ~     (p=0.380 n=10+10)
LockTable/groups=32,outstanding=8,read=5/-32     1.04µs ± 2%    1.04µs ± 1%    ~     (p=0.894 n=10+10)
LockTable/groups=32,outstanding=16,read=0/-32    28.0µs ± 1%    27.8µs ± 2%    ~     (p=0.278 n=9+10)
LockTable/groups=32,outstanding=16,read=1/-32    25.2µs ± 3%    25.2µs ± 5%    ~     (p=0.912 n=10+10)
LockTable/groups=32,outstanding=16,read=2/-32    21.5µs ± 3%    21.8µs ± 2%    ~     (p=0.052 n=10+10)
LockTable/groups=32,outstanding=16,read=3/-32    16.2µs ± 2%    15.9µs ± 5%  -1.83%  (p=0.043 n=10+10)
LockTable/groups=32,outstanding=16,read=4/-32    1.05µs ± 1%    1.04µs ± 1%    ~     (p=0.283 n=10+9)
LockTable/groups=32,outstanding=16,read=5/-32    1.05µs ± 0%    1.05µs ± 2%    ~     (p=0.323 n=9+10)
LockTableMetrics/locks=0-32                      63.1ns ± 2%    63.2ns ± 3%    ~     (p=0.869 n=10+10)
LockTableMetrics/locks=1-32                      89.4ns ± 3%    88.8ns ± 3%    ~     (p=0.251 n=9+10)
LockTableMetrics/locks=16-32                      595ns ± 2%     572ns ± 3%  -3.81%  (p=0.000 n=10+10)
LockTableMetrics/locks=256-32                    9.14µs ± 3%    8.97µs ± 3%  -1.82%  (p=0.019 n=10+10)
LockTableMetrics/locks=4096-32                    153µs ± 1%     151µs ± 3%    ~     (p=0.146 n=8+10)
TxnCache-32                                      15.0ns ± 3%    15.2ns ± 1%    ~     (p=0.704 n=10+9)

blathers-crl · 2023-12-18T15:25:34Z

Thank you for contributing to CockroachDB. Please ensure you have followed the guidelines for creating a PR.

Before a member of our team reviews your PR, I have some potential action items for you:

We notice you have more than one commit in your PR. We try break logical changes into separate commits, but commits such as "fix typo" or "address review commits" should be squashed into one commit and pushed with --force
When CI has completed, please ensure no errors have appeared.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is dev-inf.}

cockroach-teamcity · 2023-12-18T15:25:43Z

This change is

ajwerner · 2023-12-18T15:25:44Z

@nvanbenschoten this one is for you

nvb

Nice! I was recently thinking about this and came to same conclusion about a nullable pointer to a optionally inlined array being the right approach to retain polymorphism while avoiding the cost of interfaces. Thanks for proving it out. Also, thanks for playing with the padding to keep the struct size the same.

Reviewed 5 of 5 files at r1, 10 of 10 files at r2, 10 of 10 files at r3, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @ajwerner)

-- commits line 26 at r2:
s/get reduce/reduce/

pkg/util/interval/generic/internal/interval_btree_tmpl.go line 195 at r1 (raw file):

			}
		}
		in := (*interiorNode)(unsafe.Pointer(n))

Is it worth avoiding this use of unsafe and instead doing something like:

*n.children = childrenArray{}
*n = node{children: n.children}
nodePool.Put(n)

ajwerner

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @nvanbenschoten)

pkg/util/interval/generic/internal/interval_btree_tmpl.go line 195 at r1 (raw file):

Previously, nvanbenschoten (Nathan VanBenschoten) wrote…

Is it worth avoiding this use of unsafe and instead doing something like:
*n.children = childrenArray{}
*n = node{children: n.children}
nodePool.Put(n)

I'm happy to do it that way, it's how I wrote it initially. When it was written that way, there was a consistent regression in BTreeDeleteInsertCloneEachTime/count=.*/reset=true, so I changed it to this formulation which does somewhat better. Below is the diff between the current state of the PR (old) and the proposed change to avoid unsafe. Those few nanos for an edge-case benchmark may not be worth it. What would you prefer?

name                                                      old time/op    new time/op    delta
BTreeDeleteInsertCloneEachTime/count=16/reset=true-32       68.3ns ± 5%    70.2ns ± 3%  +2.75%  (p=0.000 n=40+35)
BTreeDeleteInsertCloneEachTime/count=128/reset=true-32       149ns ± 8%     157ns ±15%  +5.36%  (p=0.000 n=37+38)
BTreeDeleteInsertCloneEachTime/count=1024/reset=true-32      358ns ± 7%     373ns ± 6%  +4.30%  (p=0.000 n=39+39)
BTreeDeleteInsertCloneEachTime/count=8192/reset=true-32      454ns ± 2%     466ns ± 5%  +2.70%  (p=0.000 n=39+39)
BTreeDeleteInsertCloneEachTime/count=65536/reset=true-32     793ns ±29%     791ns ±29%    ~     (p=0.914 n=40+39)

blathers-crl · 2023-12-18T19:11:21Z

Thank you for updating your pull request.

Before a member of our team reviews your PR, I have some potential action items for you:

We notice you have more than one commit in your PR. We try break logical changes into separate commits, but commits such as "fix typo" or "address review commits" should be squashed into one commit and pushed with --force
When CI has completed, please ensure no errors have appeared.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is dev-inf.}

Before this change, all nodes, including leaf nodes had a children array. For leaf nodes, this array was garbage. Having live pointers which contain garbage is bad for tools heap analysis tools like viewcore, and has unclear implications for garbage collection. This commit changes the situation by instead using a pointer for the children array. For interior nodes, this pointer is non-nil, and points to the next word in the interiorNode struct. For leaf nodes, the pointer is nil. This has a downside of using an extra word for all nodes. A subsequent commit claws back this word. Epic: none Release note: None

By taking the two fields of keyBound and putting them into the node directly, we can exploit some available padding for the `inc` bool and reduce the node size by a word. Epic: none Release note: None

ajwerner

TFTR!

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @nvanbenschoten)

-- commits line 26 at r2:

Previously, nvanbenschoten (Nathan VanBenschoten) wrote…

s/get reduce/reduce/

Done.

pkg/util/interval/generic/internal/interval_btree_tmpl.go line 195 at r1 (raw file):

Previously, ajwerner wrote…

I'm happy to do it that way, it's how I wrote it initially. When it was written that way, there was a consistent regression in BTreeDeleteInsertCloneEachTime/count=.*/reset=true, so I changed it to this formulation which does somewhat better. Below is the diff between the current state of the PR (old) and the proposed change to avoid unsafe. Those few nanos for an edge-case benchmark may not be worth it. What would you prefer?
name                                                      old time/op    new time/op    delta
BTreeDeleteInsertCloneEachTime/count=16/reset=true-32       68.3ns ± 5%    70.2ns ± 3%  +2.75%  (p=0.000 n=40+35)
BTreeDeleteInsertCloneEachTime/count=128/reset=true-32       149ns ± 8%     157ns ±15%  +5.36%  (p=0.000 n=37+38)
BTreeDeleteInsertCloneEachTime/count=1024/reset=true-32      358ns ± 7%     373ns ± 6%  +4.30%  (p=0.000 n=39+39)
BTreeDeleteInsertCloneEachTime/count=8192/reset=true-32      454ns ± 2%     466ns ± 5%  +2.70%  (p=0.000 n=39+39)
BTreeDeleteInsertCloneEachTime/count=65536/reset=true-32     793ns ±29%     791ns ±29%    ~     (p=0.914 n=40+39)

I found clearing the children after the node does as well as the code that cleared the whole interiorNode. I think this is good enough.

nvb

Reviewed 10 of 10 files at r6, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @ajwerner)

pkg/util/interval/generic/internal/interval_btree_tmpl.go line 195 at r1 (raw file):

Previously, ajwerner wrote…

I found clearing the children after the node does as well as the code that cleared the whole interiorNode. I think this is good enough.

Strange. Any idea why that performed better?

pkg/util/interval/generic/internal/interval_btree_tmpl.go line 113 at r6 (raw file):

	items    [maxItems]T
	children *childrenArray

Mind giving this a comment explaining that it's nil for leaf nodes and non-nil for interior nodes?

If the children array pointer is set, it's a leaf node. No need for a separate bool. Epic: none Release note: None

ajwerner

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @nvanbenschoten)

pkg/util/interval/generic/internal/interval_btree_tmpl.go line 195 at r1 (raw file):

Previously, nvanbenschoten (Nathan VanBenschoten) wrote…

Strange. Any idea why that performed better?

I guess we're now zeroing the memory more sequentially? Like when you zero the child array first you're zeroing the end of the structure and then coming back and zeroing the front. I suppose when you zero the end of the node you could be pulling in part of the cache line that has the children array?

pkg/util/interval/generic/internal/interval_btree_tmpl.go line 113 at r6 (raw file):

Previously, nvanbenschoten (Nathan VanBenschoten) wrote…

Mind giving this a comment explaining that it's nil for leaf nodes and non-nil for interior nodes?

Done.

nvb · 2023-12-20T05:33:04Z

bors r=nvanbenschoten

craig · 2023-12-20T06:35:31Z

Build succeeded:

Bazel Essential CI (Cockroach)

In cockroachdb#110516, the code started used a generated btree. Unfortunately, the code did not adopt bazel code generation, so missed a regeneration when the changes in cockroachdb#116663 merged. Also, it seems, the change rotted such that regenerating didn't work because the entry was renamed from `frontierEntry` to `btreeFrontierEntry` without updating the go:generate comment. I imagine somebody did a manual rename. This fixes the problem by adopting bazel generation. Epic: None Release note: None

99884: kvserver: remove unused snapshot fields r=kvoli a=andrewbaptist This commit removes a number of unused fields in snapshot messages. Release note: None Epic: none 118490: util/span: use bazel for codegen, regenerate r=miretskiy a=ajwerner In #110516, the code started used a generated btree. Unfortunately, the code did not adopt bazel code generation, so missed a regeneration when the changes in #116663 merged. Also, it seems, the change rotted such that regenerating didn't work because the entry was renamed from `frontierEntry` to `btreeFrontierEntry` without updating the go:generate comment. I imagine somebody did a manual rename. This fixes the problem by adopting bazel generation. Epic: None Release note: None Co-authored-by: Andrew Baptist <baptist@cockroachlabs.com> Co-authored-by: Andrew Werner <awerner32@gmail.com>

ajwerner requested a review from a team as a code owner December 18, 2023 15:25

blathers-crl bot added the O-community Originated from the community label Dec 18, 2023

nvb approved these changes Dec 18, 2023

View reviewed changes

ajwerner commented Dec 18, 2023

View reviewed changes

ajwerner force-pushed the interval-btree-unsafe branch from 774e7b1 to 9829ce5 Compare December 18, 2023 19:11

ajwerner added 2 commits December 18, 2023 14:15

util/interval/generic: inline keyBound into node

6f75f2c

By taking the two fields of keyBound and putting them into the node directly, we can exploit some available padding for the `inc` bool and reduce the node size by a word. Epic: none Release note: None

ajwerner force-pushed the interval-btree-unsafe branch from 9829ce5 to cfe6684 Compare December 18, 2023 19:15

ajwerner commented Dec 18, 2023

View reviewed changes

nvb approved these changes Dec 18, 2023

View reviewed changes

util/interval/generic: avoid bool for leaf

8d33a8c

If the children array pointer is set, it's a leaf node. No need for a separate bool. Epic: none Release note: None

ajwerner force-pushed the interval-btree-unsafe branch from cfe6684 to 8d33a8c Compare December 18, 2023 19:55

ajwerner commented Dec 18, 2023

View reviewed changes

craig bot merged commit 7dded57 into cockroachdb:master Dec 20, 2023

ajwerner mentioned this pull request Jan 30, 2024

util/span: use bazel for codegen, regenerate #118490

Merged

nvb mentioned this pull request Apr 25, 2024

kv: triage microbenchmark regressions for v24.1 #122530

Closed

7 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

util/interval/generic: stop lying about live memory#116663

util/interval/generic: stop lying about live memory#116663
craig[bot] merged 3 commits intocockroachdb:masterfrom
ajwerner:interval-btree-unsafe

ajwerner commented Dec 18, 2023

Uh oh!

blathers-crl bot commented Dec 18, 2023

Uh oh!

cockroach-teamcity commented Dec 18, 2023

Uh oh!

ajwerner commented Dec 18, 2023

Uh oh!

nvb left a comment

Uh oh!

ajwerner left a comment

Uh oh!

blathers-crl bot commented Dec 18, 2023

Uh oh!

ajwerner left a comment

Uh oh!

nvb left a comment

Uh oh!

ajwerner left a comment

Uh oh!

nvb commented Dec 20, 2023

Uh oh!

craig bot commented Dec 20, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Conversation

ajwerner commented Dec 18, 2023

Uh oh!

blathers-crl bot commented Dec 18, 2023

Uh oh!

cockroach-teamcity commented Dec 18, 2023

Uh oh!

ajwerner commented Dec 18, 2023

Uh oh!

nvb left a comment

Choose a reason for hiding this comment

Uh oh!

ajwerner left a comment

Choose a reason for hiding this comment

Uh oh!

blathers-crl bot commented Dec 18, 2023

Uh oh!

ajwerner left a comment

Choose a reason for hiding this comment

Uh oh!

nvb left a comment

Choose a reason for hiding this comment

Uh oh!

ajwerner left a comment

Choose a reason for hiding this comment

Uh oh!

nvb commented Dec 20, 2023

Uh oh!

craig bot commented Dec 20, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants