On Fri, Oct 30, 2015 at 10:18:12AM -0700, Linus Torvalds wrote: > I do wonder if we couldn't just speed up the bitmap allocator by an > order of magnitude. It would be nicer to be able to make existing > loads faster without any new "don't bother with POSIX semantics" flag. > > We could, for example, extend the "open_fds" bitmap with a > "second-level" bitmap that has information on when the first level is > full. We traverse the open_fd's bitmap one word at a time anyway, we > could have a second-level bitmap that has one bit per word to say > whether that word is already full. Your variant has 1:64 ratio; obviously better than now, but we can actually do 1:bits-per-cacheline quite easily. I've been playing with a variant that has more than two bitmaps, and AFAICS it a) does not increase the amount of cacheline pulled and b) keeps it well-bound even in the absolutely worst case (128M-odd descriptors filled, followed by close(0);dup2(1,0); - in that case it ends up accessing the 7 cachelines worth of bitmaps; your variant will read through 4000-odd cachelines of the summary bitmap alone; the mainline is even worse). > The advantage of the above is that it should just work for existing > binaries. It may not be quite as optimal as just introducing a new > "don't care about POSIX" feature, but quite frankly, if it cuts down > the bad case of "find_next_zero_bit()" by a factror of 64 (and then > adds a *small* expense factor on top of that), I suspect it should be > "good enough" even for your nasty case. > > What do you think? Willing to try the above approach (with any > inevitable bug-fixes) and see how it compares? > > Obviously in addition to any fixes to my pseudo-code above you'd need > to add the allocations for the new "full_fds_bits" etc, but I think it > should be easy to make the full_fds_bit allocation be *part* of the > "open_fds" allocation, so you wouldn't need a new allocation in > alloc_fdtable(). We already do that whole "use a single allocation" to > combine open_fds with close_on_exec into one single allocation. I'll finish testing what I've got and post it; it costs 3 extra pointers in the files_struct and a bit fatter bitmap allocation (less than 0.2% extra). All the arguments regarding the unmodified binaries apply, of course, and so far it looks fairly compact... -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
