Date: Sun, 15 Aug 2004 06:51:31 +0200 From: des@des.no (=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=) To: Alan Cox <alc@FreeBSD.org> Cc: cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <xzpvfflgg18.fsf@dwp.des.no> In-Reply-To: <200408130806.i7D86YJZ075107@repoman.freebsd.org> (Alan Cox's message of "Fri, 13 Aug 2004 08:06:34 %2B0000 (UTC)") References: <200408130806.i7D86YJZ075107@repoman.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Alan Cox <alc@FreeBSD.org> writes: > Log: > Replace the linear search in vm_map_findspace() with an O(log n) > algorithm built into the map entry splay tree. This replaces the > first_free hint in struct vm_map with two fields in vm_map_entry: > adj_free, the amount of free space following a map entry, and > max_free, the maximum amount of free space in the entry's subtree. > These fields make it possible to find a first-fit free region of a > given size in one pass down the tree, so O(log n) amortized using > splay trees. Great! I've been meaning to do this for a while, but the complexity was a bit beyond me. This should greatly increase pipe performance, by the way, because pipe buffers are allocated from a single vm_map, which accumulates many more entries and much more fragmentation than (probably) most other maps in the kernel. DES --=20 Dag-Erling Sm=F8rgrav - des@des.no
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?xzpvfflgg18.fsf>