Re: [PATCH] hex: use unsigned index for ring buffer

["René Scharfe" <l.s.r@web.de>]

Am 24.10.2016 um 19:27 schrieb Junio C Hamano:
> Junio C Hamano <gitster@pobox.com> writes:
> 
>>> I think it would be preferable to just fix it inline in each place.
>>
>> Yeah, probably.
>>
>> My initial reaction to this was
>>
>>  char *sha1_to_hex(const unsigned char *sha1)
>>  {
>> -	static int bufno;
>> +	static unsigned int bufno;
>>  	static char hexbuffer[4][GIT_SHA1_HEXSZ + 1];
>>  	return sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);
>>
>> "ah, we do not even need bufno as uint; it could be ushort or even
>> uchar".  If this were a 256 element ring buffer and the index were
>> uchar, we wouldn't even be having this discussion, and "3 &" is a
>> way to get a fake type that is a 2-bit unsigned integer that wraps
>> around when incremented.
>>
>> But being explicit, especially when we know that we can rely on the
>> fact that the compilers are usually intelligent enough, is a good
>> idea, I would think.
>>
>> Isn't size_t often wider than uint, by the way?  It somehow makes me
>> feel dirty to use it when we know we only care about the bottom two
>> bit, especially with the explicit "bufno %= ARRAY_SIZE(hexbuffer)",
>> but I may be simply superstitious in this case.  I dunno.
> 
> If we are doing the wrap-around ourselves, I suspect that the index
> should stay "int" (not even unsigned), as that is supposed to be the
> most natural and performant type on the architecture.  Would it
> still result in better code to use size_t instead?

Right.

Gcc emits an extra cltq instruction for x86-64 (Convert Long To Quad,
i.e. 32-bit to 64-bit) if we wrap explicitly and still use an int in
sha1_to_hex().  It doesn't if we use an unsigned int or size_t.  It
also doesn't for get_pathname().  I guess updating the index variable
only after use makes the difference there.

But I think we can ignore that; it's just an extra cycle.  I only
even noticed it when verifying that "% 4" is turned into "& 3"..
Clang and icc don't add the cltq, by the way.

So how about this?  It gets rid of magic number 3 and works for array
size that's not a power of two.  And as a nice side effect it can't
trigger a signed overflow anymore.

Just adding "unsigned" looks more attractive to me for some reason.
Perhaps I stared enough at the code to get used to the magic values
there..

René

---
 hex.c  | 3 ++-
 path.c | 3 ++-
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/hex.c b/hex.c
index ab2610e..845b01a 100644
--- a/hex.c
+++ b/hex.c
@@ -78,7 +78,8 @@ char *sha1_to_hex(const unsigned char *sha1)
 {
 	static int bufno;
 	static char hexbuffer[4][GIT_SHA1_HEXSZ + 1];
-	return sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);
+	bufno = (bufno + 1) % ARRAY_SIZE(hexbuffer);
+	return sha1_to_hex_r(hexbuffer[bufno], sha1);
 }
 
 char *oid_to_hex(const struct object_id *oid)
diff --git a/path.c b/path.c
index a8e7295..52d889c 100644
--- a/path.c
+++ b/path.c
@@ -25,7 +25,8 @@ static struct strbuf *get_pathname(void)
 		STRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT
 	};
 	static int index;
-	struct strbuf *sb = &pathname_array[3 & ++index];
+	struct strbuf *sb = &pathname_array[index];
+	index = (index + 1) % ARRAY_SIZE(pathname_array);
 	strbuf_reset(sb);
 	return sb;
 }
-- 
2.10.1