Page MenuHomeFreeBSD
Differential D35524

rb_tree: optimize bit twiddle
ClosedPublic
Actions

Authored by dougm on Jun 19 2022, 8:05 PM.
Tags
None
Referenced Files
Unknown Object (File)
Wed, Aug 27, 2:18 AM
Unknown Object (File)
Tue, Aug 26, 11:44 PM
Unknown Object (File)
Mon, Aug 25, 10:36 PM
Unknown Object (File)
Mon, Aug 25, 2:02 PM
Unknown Object (File)
Mon, Aug 25, 4:05 AM
Unknown Object (File)
Sun, Aug 24, 8:31 AM
Unknown Object (File)
Tue, Aug 19, 10:00 PM
Unknown Object (File)
Tue, Aug 19, 2:25 AM
View All Files
Subscribers
imp

Details

Reviewers
alc
markj
Commits
rG8445e3d50ee2: rb_tree: fine-tune rebalancing code
rG2120d7f57aa0: rb_tree: fine-tune rebalancing code
Summary

Change parts of RB_INSERT_COLOR and RB_REMOVE_COLOR to reduce the number of operations, by, in some cases, flipping two color bits at a time instead of flipping each individually, in separate operations, and by using a switch statement to replace a sequence of if-elses. With llvm-14.0.3, this reduces the code size by 96 bytes on amd64.

Also, allow RB users to define a preprocessor symbol to generate RB_REMOVE_COLOR code that matches the implementation described in the original weak-AVL paper in one particular case, instead of the still correct, but slightly more efficient implementation of that case currently implemented.

Diff Detail

Lint
Lint Skipped
Unit
Tests Skipped

Event Timeline

dougm requested review of this revision.Jun 19 2022, 8:05 PM
dougm created this revision.
dougm updated this revision to Diff 107173.Jun 19 2022, 10:09 PM

Shrink the size a little more with REMOVE_COLOR adjustments.

dougm updated this revision to Diff 107174.Jun 19 2022, 10:29 PM

Undo last revision. Can't be assigning to RB_BITS. Still, a 16 byte shrinkage.

dougm updated this revision to Diff 107181.Jun 20 2022, 7:13 AM

Apply the same trick to INSERT_COLOR. This assumes that the two children of elm cannot both be red. I assert that than cannot be.

Reduces the lip3 size to 8798 from 8830.

dougm updated this revision to Diff 107212.Jun 21 2022, 4:54 PM

Use switch in RB_REMOVE_COLOR instead of several if-elses. Only modify each color-bit-pair once instead of modifying left and then right. Reduces size to 8766 from 8830 on lip3.

dougm updated this revision to Diff 107221.Jun 21 2022, 9:40 PM

Add a footnote.

dougm added a comment.Jun 22 2022, 4:50 AM

Two test binaries have been compiled on lip3 and executed on lip2. The test binaries come from -O2 compilation of this source:

megatree.c2 KBDownload
. The results of a little testing are here:
dougm@108-254-203-202:dougm $ time megatree.orig; time megatree; time megatree.orig; time megatree;

real 0m42.878s
user 0m42.991s
sys 0m0.000s

real 0m42.563s
user 0m42.524s
sys 0m0.000s

real 0m43.198s
user 0m43.121s
sys 0m0.000s

real 0m41.990s
user 0m42.160s
sys 0m0.000s
dougm@108-254-203-202:dougm $ time megatree.orig; time megatree; time megatree.orig; time megatree;

real 0m42.614s
user 0m42.810s
sys 0m0.000s

real 0m41.890s
user 0m42.079s
sys 0m0.000s

real 0m42.813s
user 0m42.773s
sys 0m0.000s

real 0m41.881s
user 0m42.036s
sys 0m0.000s

The modified code seems a little faster. Running the same binaries on lip5 produces less clear results:
dougm@108-254-203-203:dougm $ time megatree.orig;time megatree;time megatree.orig;time megatree;

real 0m26.041s
user 0m26.017s
sys 0m0.023s

real 0m25.965s
user 0m25.948s
sys 0m0.016s

real 0m26.061s
user 0m26.021s
sys 0m0.039s

real 0m26.105s
user 0m26.097s
sys 0m0.008s
dougm@108-254-203-203:dougm $ time megatree.orig;time megatree;time megatree.orig;time megatree;

real 0m25.965s
user 0m25.941s
sys 0m0.024s

real 0m26.406s
user 0m26.382s
sys 0m0.024s

real 0m26.229s
user 0m26.197s
sys 0m0.032s

real 0m25.962s
user 0m25.930s
sys 0m0.032s

dougm updated this revision to Diff 107260.Jun 22 2022, 9:17 PM

Allow an RB tree user to "#define STRICT_HST 1" to get the behavior described by the authors for the deletion, single rotation case. Leave it turned off by default, since it grows the code and hasn't so far been shown to improve performance.

dougm added a comment.Jun 23 2022, 3:13 AM

"What if you combine this patch with the one at reviews.freebsd.org/D35520, I am asked.

In terms of size:
original: 8846 bytes
with this patch: 8782 bytes
with both patches: 8654 bytes

In terms of time:
on lip2
dougm@108-254-203-202:dougm $ time megatree.orig; time megatree; time megatree.orig; time megatree;

real 0m42.777s
user 0m42.853s
sys 0m0.000s

real 0m42.260s
user 0m42.303s
sys 0m0.000s

real 0m42.649s
user 0m42.730s
sys 0m0.000s

real 0m42.232s
user 0m42.287s
sys 0m0.000s

improvment! But on lip3:

dougm@108-254-203-203:dougm $ time megatree.orig;time megatree;time megatree.orig;time megatree

real 0m26.126s
user 0m26.095s
sys 0m0.030s

real 0m26.929s
user 0m26.920s
sys 0m0.007s

real 0m26.028s
user 0m25.997s
sys 0m0.031s

real 0m27.184s
user 0m27.160s
sys 0m0.023s

not so much.

dougm updated this revision to Diff 107272.Jun 23 2022, 6:13 AM

Fix typo

dougm updated this revision to Diff 107370.Jun 25 2022, 7:51 AM

Update for overlapping patch just checked in.

dougm edited the summary of this revision. (Show Details)Jun 28 2022, 7:13 PM
dougm added a reviewer: markj.
markj added a comment.Jun 29 2022, 4:37 PM
In D35524#806424, @dougm wrote:

"What if you combine this patch with the one at reviews.freebsd.org/D35520, I am asked.

In terms of size:
original: 8846 bytes
with this patch: 8782 bytes
with both patches: 8654 bytes

In terms of time:

It seems a bit strange that one test run has 0 system time, while the other does not.

sys/sys/tree.h
538

This could be prefixed with RB_ to reduce the likelihood of a collision.

dougm updated this revision to Diff 107560.Jun 29 2022, 4:47 PM

Rename STRICT_HST to RB_STRICT_HST.

alc added inline comments.Jun 29 2022, 5:49 PM
sys/sys/tree.h
496–497

Why is this flip no longer a part of the prior "else" clause?

dougm marked 2 inline comments as done.Jun 29 2022, 5:58 PM
dougm added inline comments.
sys/sys/tree.h
496–497

The only possibilities for the state of 'child' are red-left, red-right, and red-neither (when child is a leaf). So the 'else' doesn't matter. Removing it, though, might prevent a branch instruction.

alc added inline comments.Jun 29 2022, 6:08 PM
sys/sys/tree.h
496–497

This change is more likely to be a pessimization. When RB_RED_LEFT() is true, the code now has to perform another conditional branch on RB_RED_RIGHT().

dougm marked an inline comment as done.Jun 29 2022, 6:21 PM
dougm added inline comments.
sys/sys/tree.h
496–497

Making the RED_LEFT test conditional on the RED_RIGHT test failing leads to an object code of the same size, but with two more 'jmp' statements in the compiled and disassembled code. Let me know if you want to see the diff.

dougm updated this revision to Diff 107576.Jun 30 2022, 3:26 AM

Swap the order of child color tests in the color insert double rotate code, following a verbal reviewer suggestion. It reduces the object size a bit more. Now, from 8686 to 8574, for iommu_gas.o.

dougm updated this revision to Diff 107619.Jun 30 2022, 5:42 PM

Update after placating coverity.

alc added a comment.Jul 2 2022, 5:53 PM

Give me a patch that only updates "insert color". I fully understand that part, and I'm ready to approve it after a little testing.

alc added inline comments.Jul 2 2022, 8:07 PM
sys/sys/tree.h
352–353

This being done as two separate assignment statements is pessimizing the generated code.

dougm added a comment.Jul 4 2022, 3:15 AM
In D35524#809486, @alc wrote:

Give me a patch that only updates "insert color". I fully understand that part, and I'm ready to approve it after a little testing.

https://reviews.freebsd.org/D35696

dougm updated this revision to Diff 107722.Jul 4 2022, 6:36 AM

Rewrite RB_SET_PARENT. Upcase the /* fallthrough */ comments.

alc added inline comments.Jul 4 2022, 7:24 AM
sys/sys/tree.h
530

It seems odd not to have a blank line separating this comment from insert.

dougm updated this revision to Diff 107724.Jul 4 2022, 7:26 AM

Normalize with a blank line.

alc accepted this revision.Jul 4 2022, 5:21 PM

The effects of these changes extend to arm64 as well. vm_phys.o's vm_phys_fictitious_reg_range() and vm_phys_fictitious_unreg_range() are together 140 bytes smaller.

This revision is now accepted and ready to land.Jul 4 2022, 5:21 PM
Closed by commit rG2120d7f57aa0: rb_tree: fine-tune rebalancing code (authored by dougm). · Explain WhyJul 4 2022, 5:33 PM
This revision was automatically updated to reflect the committed changes.
dougm added a commit: rG2120d7f57aa0: rb_tree: fine-tune rebalancing code.
Herald added a subscriber: imp. · View Herald TranscriptJul 4 2022, 5:33 PM
dougm mentioned this in D35696: rb_tree: optimiize insert_color.Jul 4 2022, 5:34 PM
dougm added a commit: rG8445e3d50ee2: rb_tree: fine-tune rebalancing code.Aug 1 2022, 5:47 AM

Revision Contents
Changeset List

PathSize
sys/
sys/
99 lines

Diff 107619

View Options

sys/sys/tree.h

Show All 36 Lines
#include <sys/mutex.h> #include <sys/mutex.h>
#include <sys/pcpu.h> #include <sys/pcpu.h>
#include <sys/proc.h> #include <sys/proc.h>
#include <sys/socket.h> #include <sys/socket.h>
#include <sys/socketvar.h> #include <sys/socketvar.h>
#include <sys/time.h> #include <sys/time.h>
#include <sys/uio.h> #include <sys/uio.h>
#include <netinet/tcp.h>
#include <rpc/rpc.h> #include <rpc/rpc.h>
#include <rpc/rpc_com.h> #include <rpc/rpc_com.h>
#include <rpc/krpc.h> #include <rpc/krpc.h>
#include <rpc/rpcsec_tls.h> #include <rpc/rpcsec_tls.h>
static enum clnt_stat clnt_reconnect_call(CLIENT *, struct rpc_callextra *, static enum clnt_stat clnt_reconnect_call(CLIENT *, struct rpc_callextra *,
rpcproc_t, struct mbuf *, struct mbuf **, struct timeval); rpcproc_t, struct mbuf *, struct mbuf **, struct timeval);
static void clnt_reconnect_geterr(CLIENT *, struct rpc_err *); static void clnt_reconnect_geterr(CLIENT *, struct rpc_err *);
▲ Show 20 Lines • Show All 48 Lines • ▼ Show 20 Linesclnt_reconnect_create(
rc->rc_retries = INT_MAX; rc->rc_retries = INT_MAX;
rc->rc_privport = FALSE; rc->rc_privport = FALSE;
rc->rc_waitchan = "rpcrecv"; rc->rc_waitchan = "rpcrecv";
rc->rc_intr = 0; rc->rc_intr = 0;
rc->rc_connecting = FALSE; rc->rc_connecting = FALSE;
rc->rc_closed = FALSE; rc->rc_closed = FALSE;
rc->rc_ucred = crdup(curthread->td_ucred); rc->rc_ucred = crdup(curthread->td_ucred);
rc->rc_client = NULL; rc->rc_client = NULL;
rc->rc_ddp = false;
rc->rc_tls = false; rc->rc_tls = false;
rc->rc_tlscertname = NULL; rc->rc_tlscertname = NULL;
rc->rc_reconcall = NULL; rc->rc_reconcall = NULL;
rc->rc_reconarg = NULL; rc->rc_reconarg = NULL;
cl->cl_refs = 1; cl->cl_refs = 1;
cl->cl_ops = &clnt_reconnect_ops; cl->cl_ops = &clnt_reconnect_ops;
cl->cl_private = (caddr_t)(void *)rc; cl->cl_private = (caddr_t)(void *)rc;
▲ Show 20 Lines • Show All 90 Lines • ▼ Show 20 Lines if (rc->rc_tls && newclient != NULL) {
rpc_createerr.cf_error.re_errno = 0; rpc_createerr.cf_error.re_errno = 0;
CLNT_CLOSE(newclient); CLNT_CLOSE(newclient);
CLNT_RELEASE(newclient); CLNT_RELEASE(newclient);
newclient = NULL; newclient = NULL;
td->td_ucred = oldcred; td->td_ucred = oldcred;
goto out; goto out;
} }
} }
if (rc->rc_ddp && newclient != NULL) {
int optval = 1;
(void)so_setsockopt(so, IPPROTO_TCP, TCP_USE_DDP,
&optval, sizeof(optval));
}
rmacklemUnsubmitted
Not Done
Inline Actions

Normally the clnt_rc.c (reconnect layer) would
do a CLSET_TCP_DDP and the so_setsockopt()
would be done for CLSET_TCP_DDP in clnt_vc.c
and ignored in clnt_dg.c.

I've never been much of an object oriented guy,
but the Sun folk loved these layers.

rmacklem: Normally the clnt_rc.c (reconnect layer) would do a CLSET_TCP_DDP and the so_setsockopt() would…
if (newclient != NULL && rc->rc_reconcall != NULL) if (newclient != NULL && rc->rc_reconcall != NULL)
(*rc->rc_reconcall)(newclient, rc->rc_reconarg, (*rc->rc_reconcall)(newclient, rc->rc_reconarg,
rc->rc_ucred); rc->rc_ucred);
} }
td->td_ucred = oldcred; td->td_ucred = oldcred;
if (!newclient) { if (!newclient) {
soclose(so); soclose(so);
▲ Show 20 Lines • Show All 292 Lines • ▼ Show 20 Lines case CLSET_TLSCERTNAME:
rc->rc_tlscertname = mem_alloc(slen); rc->rc_tlscertname = mem_alloc(slen);
strlcpy(rc->rc_tlscertname, info, slen); strlcpy(rc->rc_tlscertname, info, slen);
break; break;
case CLSET_RECONUPCALL: case CLSET_RECONUPCALL:
upcp = (struct rpc_reconupcall *)info; upcp = (struct rpc_reconupcall *)info;
rc->rc_reconcall = upcp->call; rc->rc_reconcall = upcp->call;
rc->rc_reconarg = upcp->arg; rc->rc_reconarg = upcp->arg;
break;
case CLSET_DDP:
rc->rc_ddp = true;
break; break;
default: default:
return (FALSE); return (FALSE);
} }
return (TRUE); return (TRUE);
} }
▲ Show 20 Lines • Show All 48 Lines • Show Last 20 Lines