Re: slab: avoid linear search in kmalloc? (GCC Guru wanted :)

[Andrew Morton]

Bernd Eckenfels wrote:
> 
> Hello,
> 
> I noticed that kmalloc and kmem_find_general_cachep are doing a linear
> search in the cache_sizes array. Isnt it better to speed that up by doing a
> binary search or a b-tree if like the following patch?
> 

Possibly.  I've never seen it on a profile though.

Just for kicks, try feeding this into gcc and take a look
at the assembly output:

int thing(int size)
{
	int ret;

	switch (size) {
	case 0 ... 2:
		return 1;
	case 3 ... 4:
		return 2;
	case 5 ... 8:
		return 3;
	case 9 ... 16:
		return 4;
	case 17 ... 31:
		return 5;
	case 32 ... 64:
		return 6;
	case 65 ... 128:
		return 7;
	case 129 ... 256:
		return 8;
	case 257 ... 512:
		return 9;
	case 513 ... 1024:
		return 10;
	case 1025 ... 2048:
		return 11;
	case 2049 ... 4096:
		return 12;
	case 4097 ... 8192:
		return 13;
	case 8193 ... 16384:
		return 14;
	case 16385 ... 32768:
		return 15;
	case 32769 ... 65536:
		return 16;
	}
	return -1;
}