Re: {RFC/PATCH] micro-optimize get_sha1_hex()

On Sat, 9 Sep 2006, Junio C Hamano wrote:

I _suspect_ that you profiled using "gprof" and the "-pg" flag to the compiler?

The thing is, that generates almost totally bogus profiles. It makes simple function calls look extremely - and unrealistically - expensive, because the profiling code itself adds lots of overhead, and it then ends up showing on the tick-based profile too in a way that it wouldn't show in real life.

It tends to be much better to profile unmodified binaries using "oprofile", which doesn't end up giving the exact number of calls, but where the time-based profiling is a _lot_ more reliable.

That said, clearly "hexval()" can be optimized, and it's quite possible that it would show up even in oprofile data too.

I doubt it's 5% in real life, but your optimization looks fine to me.

You can make it even _more_ optimized by not even bothering to test at each point, but just inlining hexval(), and making it a single array lookup. The point being that if you get -1 for _either_ of the two lookups, since we shift them and or them together, the end result will be invalid, and you only need to _test_ once.

So this patch should generate much better code, where the inner loop is something like

<get_sha1_hex+16>:
	add    $0x1,%esi		# count of result bytes..
	cmp    $0x14,%esi		# did we have 20 already?
	mov    %dl,(%ebx)		# save the "last loop" result
	je     0x807630b <get_sha1_hex+75>	# break out
	add    $0x1,%ebx		# update dest pointer (one byte at a time)
	add    $0x2,%ecx		# update source pointer (two hex chars at a time)
	movsbl (%ecx),%eax		# get first character
	movsbl 0x80989e0(%eax),%edx	# get the hexval for it
	movsbl 0x1(%ecx),%eax		# get the second character
	shl    $0x4,%edx		# shift first character hexval up by 4
	movsbl 0x80989e0(%eax),%eax	# get second character hexval
	or     %eax,%edx		# get the byte value
	test   $0xffffff00,%edx		# was it ok (0x00 - 0xff)?
	je     <get_sha1_hex+16>	# yeah, continue

which should perform very well (just two comparisons - one for the "wrong bits set" at the end, and one for the 20-byte-counter test at the beginning). Small and sweet.

In fact, I don't see how you can much improve on that code even if you were to hand-code it, so gcc actually generates good code once the "hexval()" function has been written like this.

Not very much tested, but it looks obvious enough.. And it's actually conceptually a smaller diff than yours (ie it doesn't change anything but the "hexval()" function, and all the bulk of it is the stupid array initializer).

		Linus

---