Subject: Re: rbtree for vm_map
To: None <matt@3am-software.com>
From: YAMAMOTO Takashi <yamt@mwd.biglobe.ne.jp>
List: tech-kern
Date: 08/26/2003 00:21:34
--NextPart-20030826002006-0197300
Content-Type: Text/Plain; charset=us-ascii

hi,

> > i'd like to bring in uvm_map rbtree stuffs from OpenBSD.
> > (patch attached)
> >
> > any objection?
> 
> Have you benchmarked the changes?  Does a build finish faster with 
> them?  Does phoenix/mozilla/etc load faster?  How much bloat does it 
> add?

i did some benchmarks. (attached)

YAMAMOTO Takashi


--NextPart-20030826002006-0197300
Content-Type: Application/Octet-stream
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="uvm_map.rb.bench.tgz"

H4sIAGQfSj8AA+w9aXfbRpL5Kv6KjjLekWKKQjdu5XhjS3aSt3KskY+8XY+fByJBCjEIMACo
w1r/962qboC4CFIayruZJ8Siuqvr6rq6G4CYMJ4Mpt5sEPnZWToazEIviL7a8KVxTbMM4ytN
07htavhb47KPl7AN/SvNtoUQhiF08RWO6jqMb1qRtmueZl4CIjPvo5eeBx14fpJ+CYW+7MWZ
urSBxlnieyErQTSG065C0uu0J7QFiGsNMt4gc4nMKJO5DTKzTsZ1IrNKZMJpkBl1MmEQmVMi
0+3VZLogMgjWBcxo0PGGTYC3tEmJztUbdI3Z2Q7R6Qs6PtAbVhE1PTlyksYs0TlmnU7ndTpT
WtNc0AnEqtM15Lm28kKJzm64AaxQoRMDQ8aKvaDTcTY1OkOr0zm5+0p0VsMuZk1PfcAlnbug
MzCC6nRWnQ4gyu8lQrMh0DbrhI40aK9XTqJmNixLIl6KF61hlxYyvRmfZpNO1OlMXo9PiLNG
vNTjkw+EVo9P8GlDnmj4T6WfUfaf3TAnt+vmtEQ9Pk2Mjnqc1eZnDrRGfNoDfSWdNXCteny6
A6Nhl3p8urkfFvHJIf+sRpy5FTrAEWYtPrmBsVejs/QqnT5wtXp8cntgNAxqVR3IrYEjDdpZ
/8Pq+p+c3cMac4v1H4LNxPVft3T+sP5/geu26z9vrv+NlGmWILWQl9d/0Vz/9cZCbjXWf6NR
0JvS1MJTXv/N5vpvN8jcZn21RYPOqdNZRrO+Gg06rjfqq9usr7xRXzmv11flA6NM5zTMUq93
YmBq9fqqt6wfemOZ4069vhromXqdbC6PjfXfwL1EXV61TuLSa9fXf7Nt/ef1dYBb9fXfGuiN
fUpdT3Pg8sb6b6Ob6/XVri8guru59b8Zn00yuyU+G37QrDqd3bL+N7c3ohGfurXW+t+IMyGa
67/eyAfh1uNFa+xPDdxd1P3n1OlsUY9PiIWGvDqdkeetXY4XrUFnNuLFsOrxCXuJRhGs01Es
1uLTHjgNv9s1P9j5vrYcn07LBtzR6oRq495Z/3H9v/TCj/d5A2DF+q/RWV+u/6YwLDr/m9x8
WP+/wAWLgjAtDC2hGQasrhozhaZDbRJUaUwucNDQHAfyTGOua1mOA4NYTrgmDBx1uMOBEdDo
mstNAcOG5OjgMLdgOwdVVmMWyLItznTKVl2zibkwhGtoOM65Y2oO1F6D0svQXFJNF7awbdSN
u7rBbTg7mDIfpHqIaXAdFgBgZoN+FneZ1R34Dxdd9fy/jwPA6vxf7P+hAFD+a/xh//8lrrb8
1x0B61l7/nNINBf2CssKADjYgVRfVgAMnXPLMWC8vQBYpmWYtg3j7fnvuJrFiX5J+nMoQDpM
ADD+r037p7go94f3K2NF/kPO8zz/IZx0zH8O68RD/n+Bq/dNEA3D+chn38NecX869aLB+Y81
aOKn8TwZ+s2ReRAjsAT1k6SKNh5GWVijzEaSrgIKg7MqbB4FAJb8R/44iPytkyc/Pfvw6pf/
fsa2sDgU8F9fPDnZ2sJytAAdv3xZh52cvABIrzc89xI2mk+n1+wHpn3X6wVR1pvCzncHGsxL
JsM+I5xvoX3x7v1u76a3dREHI/btxey73hZiBX32OzTT4JP/IWNTb5Z+AmYLBb9lIE3hzpI4
w8HTl68/nD57cqTAEVABGJVXkPEoHwrjmMZwFgAbxlGaKZ3GQehH3tSH4e39kX+x/8lP4m1F
iAktJ7UVxtEEZATROMyqIO/3Ggiie1hBmXkTX9lmKxizHbQJ+5HxXQaWIMjXaZYMp7MdshB/
32fbKHp7V2JsKT34d9ipzAYswzUCI9O9vbx58fgxNj/34F9NKICVrbwsDnKRu99V0ASilWxD
WOI9zmA8gn4886OdfLzPXn44PXr56/F/5VwA53umIQ8I4R0O80GC7V2ijxO28zvZg/0OaDQf
aD5+LGcrQwM0fIdqkkhJE0iaAGlgBFo5ydYFTgfybbbz65vj476MoD6FSp9BRHx4/svxs//B
xqufn5w+O+pDcPRBQTIXKowMfpCYTwD1CFVfKI+ctyUy6hW8B2kUu2hgokcPKV0wcD5+l7fi
8bhoR0BGpqdwZvtM0BD4fj7MWDJPMU6SudaHD07zJt4TP5NjO6dvXlFKPDt+3mf/AZi7VT0L
TC5NrQwnY5h9RMPBr8JqWzIFhjSTrS1QFRATLxrt7C4gj8o6S6ZbQzI3WAIR9nHgPXtcSdcd
IsURxUoWiMc/FOI+rzE/nidAc4ZC+UOykSkG3COZIipPAQBMBsn8gwLsoXkXfYUsM7iELAEL
ZOoTMuX24x+wifcFdhRFmgVTf5BdfMBhTEm62OMcr46GbHbZXomNth4brckmD8NVOYKmns4R
uiODWKVJLYYiQtneLcrH1jCMUx9SejevXxTsMDxLIKrHO9uPwhGr/fwj2u73pNLkm35eO/t5
xexTnZSf+2qQJPhXQbaDqfn5z7brxGc/szC7Vxkr9n+W4Jbc/xnc0nDfp9G2/mH/9wWub77e
n6fJ/uzjZP8siPYn0XwWwl5lbwazhd1X75veN5gQ8nPrJ/Yre8NO2DF7yV4r2FvEjCO8Ectm
XjY8D/0LP2S6Gg492LdM41EwDvwRe30+Z0dQKLhgXD/QNPjHfnrxGk6KmlAEr67TzJ8esF/9
7OmrI8YH1m8VHQ7j2XUSTM6zncNdxl3HgqLHXVfv46cDnRKv1+fx1EvZb0EYBt407bPDOAwi
9p9+GPrXDFYNKCfRNYuzc5hERcrr65nP/nnuh7N/sixm3nDopykDPBZHe8ADFj1/7Cd+NPSR
x9wLC5E+y634/MnfWZAy78ILQu8s9Nk4iacK7zzLZgf7+5eXlwOFPoB6Euce2Bt7fwzOs2lY
0eqVDyoP4+nUj7KU9E/8P+Z+Ch0spaguavs9ctpTnP428pJsGs+z84E/mv9Y5nQ2n4BN0vlk
AizAh5IlOCslLjDcyQQ+Uz9jmZ9AKfRCdsV5DgPM2TzrYTOKh2EwY7MYCm9KEOrHkV8ezi5j
6p7B6s4HsjBIQJyM/ITpnOHyBp+XcpwGr0Ze5lHrumh9KlpXYjG8aJ7FV5fBKDunjlzir/rX
1AMbTj2gY9uP2GS7DLpugq5EC1oL7FMJ5EWT0E9hvzIKvChV858kwYiaHyEmsyCDONneLgAU
6uCOGTulVhQnkF9J6uNEGEZihqG6J6hNM5MGYqk3ncFmlxksnXnDAHb1nMlxTUmGoPRD1faS
JL7M4cApza7D3ENhPEmHnurCLgl+pQy2fOofgaV/4TDEOPUhMyDpQSgcvbx5mMfCDIQmedtL
YCeeJcGQABeBf8ksYKjDDyzrko+cRYobiz5+EDBI4wUcwRJ1noy9YRFWcZTBqVVFHM6U/fWR
M9AnfyUQLHwzVG8Ige2n4A5Fdh6MRn6kS4/A0TUhLZmMQqMGRUOp6ZSAWP8gleaQQ2ZtTFpJ
gclaiQeZhzeu+nK+MTgcSpTWl3PCsGXkCxKWltJoPI+GmLXlYRn3eB70rqDyYMqIWsqIrtHr
zsFO0iwYpiyIirZcBrSBWUAwhCAGc9D0ikjK8TG9boKuRAtaEyaZqWoxDSCaE8yVOPMyn3wx
hlLJ5DzWR/1URo3ibuQolrqqzvWio7IaYm6ftqoMd8Pb9JQXr37eYHnm4zhsTKYzAID4LIun
C6nLyRI4CcGh4h1sxA/g532pWkTxZRJk/pk3/MjYN2xnOE9g9crCa/ZuT/E54LLxnu1KJe7G
zVTc1O+c23yj3C42yu1K1gc4SECmj9nCT/Es7XLTlVCEq3w5nmawDIz2H033H13/I3r088Gj
F4pFPhFFB9PBMxQ+/18yKSX5bgZQLq67+lrNAw9xsPWjG/vrm+F6HTNct02Ump0Tvd7sRD+t
oemnzUqEmsm4v6c51A2nXoIFfk+W+7NqN6l2s2o3jKmEbh9u92h/ud14e28bjtEamzN+YEHc
lW4P9tnlvtyeb/dx9gEU4gVa4k/msC4zvDtWxQxb/j6gU0i8vpQcVe4mn718/mc7PP8bXPT8
555vAKw6/2u2UZz/dUHPfwQ3rYfz/xe4Hs7/D+f/h/P/w/n/4fz/cP5/OP/f8/kfnyqRxiyG
FD73vdHDPYD/x/cAvtjRfyPnzHu6I4DPOjd39t+Mag+3BLpvCTRe6N+mU/jOX8z9v+i7dBav
HNSbLwG3ETyc1v8NL3r+f8/n2u7zv87pnU91/uc0zqHx8Pz/S1yPvj55tfdkFJ/5e2Kg9R49
eo1blQMm4wL6h4nvZXFyUBxqG+d8hQM70SPYmRywF7AlfTKfMGEyoR8I88DQ8UyOiEfxcI5n
1+ewN08P2A7gR6NdGHgazyM8LTyNrw6YqdE/02C2jSq9TAKgIQkH7BiOqLCTnPkwcAL7qQqb
Z9HoUJ2Oe3iSHgXDDN9vZ9SA7WIvB575UER7+4dwtknY2AuhkOPw/is4/IzKACBYHKxoyyDh
GA+LgQoWjV9AMI1hl2xYsj8K2Q3X2HQefpaA81n2AY61A1PhV7swyggjH2QXRe8Fu5nCBjKL
P7OzAA7sBDxmN3QYrABP2U3SRH0L0CYu8BcohAlUstBCoBpl2HF6Hl+yG6bWOTqQwBEkiT/6
7EWPwVFGTf2UEaaa7ukKstF8hl2IAWnEGZx4I3/SzuzwDszgvDIKLtr5vTkBZkhERsapksn9
qyF5U3qCwOclMAhqsRBrsWQu5wi8xGTM3cDqnUzOhtSRUXeDar57/5kFY7AijI+gIrHPPTmQ
/3TgYs/HyFXinqI4ZZZqvErNgGwBUjRPOmjQfm00b46V+SppQPaqsihZDi8kofs6NBtOk5E5
AoSQMIX9lZyTpbq1aXX8+gzQwQbv3jON/gPzF2MejMFc33GGklCkyFvvS9aXhGVfFRw04HBC
3HmDO1djBhsh4xHx5DUkoZBwnOkKCdHKSLpC4ohE5SGUAqtohkIzc4GMV0VX0c2yfnqBrivu
dU2tsqaLD6PQuYput6PXCfFWgF4jdVaRNqSDSfKfBaMTqAdFqLwrORQjb5J6F3gjQgUNLCbs
Bc3hbU4xSeDkDTv8Im8Dr50daDKMZ9eU7d5oRMUHqwFVLvX7LUGKnsLA/tsK7ltGb63C2nqu
RAEqTiSfU5guUQKp0/kZzYKKDwpZVhvr6p0yqmGL2QNOXj/iq+5pU4KeK+nUKRtCKVPYQAop
qXieD2srJ3+YLJt8tw7nqhbnanRYJVfltERURIRS43USvFkdCRz//hxLSltI7HH8phsczUNB
9rSin2MuEJcZJ1frFexhQS2lAgYK2mvhxed3sl3FfwsHLvVgSctxEIZlmy1T4L6tVdPj6Ba+
o4RaKmOFMnvr+w7VWss896AQmmdR4rq02GRxKzvlxF9WqXOnULUGvngnMg3p3idxfgELwA1+
P4u6IUrA488s8WdwGumxht0XVb1cVPE0skSBDUimqdZXk8MgGYZ+56yVHTWmWxrzkmGOWq6I
xGWZ7lXqssUPtdKuqGZreVYgh7kaM+AURuTlY8IhX06uLslF7fGKsQvSyJUKVS2Uo+bXRUX5
BW5FD7FqGm0KgHjubEwF/S4qbFQD4y4aoHxhb0wH825WkJFQG9u80hVVrTVVrYXMWnLXspV9
BwU2Kd+5nXw6xNptXO+qgHsHA6AGWIs2owHvqH/NMrh69l2Ru/mSwzvK791rzkoGawfBmrO4
U/HGOWxSibbyvX7luqspNz2LOy0B7t10qEruKPzLVL/rNE/9IWDewHbyksYMhtsv2NSoVOUM
UP0r4KPubEKLzjOqm8uUR5Ucp13Wqz/mXuKrO1oouDz4NM1H80N3cWwqdwRTXCqMV++86GhV
6Ae4ubwKn44agORKNG36Wuk7sq91Nqs5duyEltgHIWjc5Tw7ArtdS+yspW1H4LabMQ+ff1Fu
x/ajmzNZrNtaHTuLW/BuWb9azNCqQMfW4lZG6tgh3NIkXSv9MpXWTYNOU3Qt0ncRXM2WbtG3
zm2lzDoZ2bpi3p55d5AtEX3XatAp+o7VrmvlywmWUh9hVMpb0IsbC/i90/ndBI3BQtG8EV3i
wFdz4N0cxGoOopuDvpqD3s3BWM3B6OZgruZgdnOwVnOwujnYqznY3Ryc1Rycbg7uag7uioha
Iyj5qqhcJyxXxCVfIzD5isjka4QmXxGbfI3g5Cuik68RnnxFfAbesy90U7b6nONpfLVM8H0+
8yk/Muia+P0/YCnfnV9Lk3t7XFC+U71Mk3u4R166y7xM6rKb1Ir05cz7Y+4XObAQRU9eJ4l3
Xbs9rhXw8sEsT4Tf7jURlLKNLFgmdZNZ0CobU6BryptPgWVqHK2lxsbiv1UNDP5latw5+KuS
2iJ/mchG5C8Ln+cY4HkG4CZ0WeznD3Kvp2dxuPfyLAyQn+oDbjQax1GGr4FobMAtW75z8p5N
vY8+jvTwZkXoRxN8/6x4wY3d5DdG9p//csT8P4pXiT6zGxCYvzD0Gf9YyYPtsXo8Thx8uQoF
EQlAoh6A5Ft2Jwn+UZB6Be8A3xipvVknnSLf5Csc08P/fZLG5Kf8iyJXU/7paWzP1IwKdm6r
nrrt09v52Q8v/CwYersLm3BDMaMekJA95N9AvTnuHb8+61m6xgyhQYBaOoWfJSwXGqe9PQUw
DUth7DBtl9HbakTGhdVFB79NnSA7TJTpBM5xPTqjQuca69JZZTrddtalc8p0htVplzIdrxhG
WktjgPgWfhlctwELvEgAmopT2JNe2Otxx7VW0MFvQ9i2tKdWUOocRtenNBaUhiHcW1BaC0rT
upW2zoISCMUtKPH7HgoTLQtbndaQHgGUYxQoxzruYSYIkwgq77nUN6FF0tEmFFy0/Gsfcr3y
QtXTbbCKTVRt35ZROAzRDEcnxOr3ntSmelKeswazgTOCYTg2ErZ8fcEiBF0zx9NdV1kCHWYA
hAvOTA4gSF9mGtSwmemqhu6oIRWrOhO2bBlM10QO06y85RQtS1MtXeQUwnByGOznc1pRUugk
THu2aTPDNqntODozIS6xzTU4WJmOIzsYJZCEsiNAPctRaJg7GFfYEaasTJIzJQc3wCnUQ8tz
25Q8KPyFxmXP1ICB0HXJkgJcmGBC7Fk6YrqalEAhrHNNSrBM15DGJlVaHMeV43SDHNf+hRJV
30nUqu8wXMBOAh1lwoSwHDUcZPHc3AYvHJTj6aBkPmrkFAsYL/CU06TUwwSnDCXGcKlNpre5
IztkepdTR5peNwX1pOmRknpketeRY9L0uiU5StPbXGKS6XVcIkgymh4m4yo90PQ2rPHUI9Oj
rUiVFtMLZXqhNXMmbjO8RGwaHpOmyAxuq1wxrDxpdDUkcqvzwifczAOfFwmC39OetwoKx8wp
hFVwKVrcKCmEL7XJrDEd2cG0wRSijswb0EX2MHHwTwZkD91nFpjoP9tQTMiBrqbLnnSgZuVd
8qAAa1OXXMgNoUjJh9ziCpmcCDZwZZe8yF2upJIboQzko+RHNL3UqcWR+v+2d7a7acNQGP7d
XIXXVVP3AxZ/xUkndiWVJgapOq2FCajEpF38fOw4OAFCaAfVuvdIdXHw8febEyQeXC1kmu3U
0M619GV3iojLIKK0lkmRVtOvZJCENkESWRpemSIsXW7IgyKVSk3Ugn229YKxZei1v1fZil3G
CUb4TCUYK1rK+fmmZxyXM+4OZEVHOTfbUipfo5tsJbjP+emj0VKu+iJdHZTouZQmhQBbYlgW
Yztni23gpH583MAj/P/G2Pzvv5wWbDrAf6VSb/3+CzcGv/9/DtvHf1X74qUAWFrcKHXDAYAB
AAMABgAMABgAMABgAMAAgAEAAwAGAAwAGAAwAGAAwBgAMABgAMB69R4AGAAwAGAAwACA7UM+
AIABAAMABgAMABgAMABgAMAAgAEAAwAGAAwAWLcEAIABAHujAJjhqgWA0TfRY9Bpw9pEIBe5
5eqQmy9h3YY6dmyRY23PQc1aXTPZ8Mvy3n7NFlvMWZenavjpzqlp+LVaLDpnJ/Zs+EnZe250
s8UW59blmcV+Dpvq6ddssUXIdXmaVosdAJibvS1AjtCco8Cx2rPIDrW4B60TxB7195QRlEdf
zn8WlCdzeUybOsb5jgIBY5wvPWqcJvI0/BicLwYBpS3V37P4+whhdOMjTK2FEIZLodQLEEI6
J2obFqR1bsOCy+YuqBjB7bPRjuAE98AxTTqQpyJjucnpkt24A8/CCF2RfFyowt7KPTRog1ae
Z/XVLAtXTcHjqhwOR6I1AeAjHXJrnsUjhfBCi4rFy4hUk76k21XSBMLOrbcq9PN4uz6Enes0
9aUav+HV+AsavutqoSXtARqoNmH0vB78gOdxPQ5Io8HnuWfj3OALozwMFyr0LJzDrLjn3dzQ
XTU172Y3cL6DdwPoc2JbPM3c+d7L+9O1ceD851Rz4fkfIbTdJ+78Z5Vq8D9nsPfvmDv42X6m
GZRJQqcIr+0nBnabcPtn48BtoijJKMkpoWdMeodSmfoClOrUl6PUpL44pUVaedG/z2w6Z8lF
Obmfs8GMXa2TC3f+NHWB2HA2/DQezp9W9h1Wg6xMfPnAkymdGJyQp0/afeVn7Vx4uenaa6/k
84z0f0rtkx3SvwjnvwklMi38+W8C+j+HtfQ/Gz+Wo6vr5a/lZPVAIngcT+6n5c/ht/l8VU6/
/igXs/LhY2KDsJXAJniw32xVlowOkqQLV1TPpoyDCRuF3BVf6h8VzhuxaHlO1sZB/UsV9M+V
yVz8t4+I0P8ZrKX/6ZR9vxttIu/8brRer9lk/jRbjXJeiEbY1e2Qq6Iwm3eE1ksbQS+TixBE
aQNSUKWmolj/2nMDg8FgMBgMBoPBYDAYDPYW7A/FIDjOAMgAAA==

--NextPart-20030826002006-0197300--