Skip to main content

Browse the archive

https://github.com/torvalds/linux
05 April 2024, 19:05:47 UTC
Revision c63e09ecccb50f930e899d7005edc5411ee86d4f authored by Al Viro on 24 June 2009, 06:05:18 UTC, committed by Al Viro on 24 June 2009, 12:15:25 UTC 
Make allocation of anon devices cheaper
 
Standard trick - add a new variable (start) such that
for each n < start n is known to be busy.  Allocation can
skip checking everything in [0..start) and if it returns
n, we can set start to n + 1.  Freeing below start sets
start to what we'd just freed.

Of course, it still sucks if we do something like
	free 0
	allocate
	allocate
in a loop - still O(n^2) time.  However, on saner loads it
improves the things a lot and the entire thing is not worth
the trouble of switching to something with better worst-case
behaviour.

Signed-off-by: Al Viro <viro@zeniv.linux.org.uk>
1 parent 7e325d3
History
Tip revision: c63e09ecccb50f930e899d7005edc5411ee86d4f authored by Al Viro on 24 June 2009, 06:05:18 UTC
Make allocation of anon devices cheaper
Tip revision: c63e09e
File Mode Size
Documentation
arch
block
crypto
drivers
firmware
fs
include
init
ipc
kernel
lib
mm
net
samples
scripts
security
sound
tools
usr
virt
.gitignore -rw-r--r-- 945 bytes
.mailmap -rw-r--r-- 3.9 KB
COPYING -rw-r--r-- 18.3 KB
CREDITS -rw-r--r-- 91.7 KB
Kbuild -rw-r--r-- 2.4 KB
MAINTAINERS -rw-r--r-- 147.7 KB
Makefile -rw-r--r-- 53.8 KB
README -rw-r--r-- 17.0 KB
REPORTING-BUGS -rw-r--r-- 3.1 KB

README

back to top