libgit2/libgit2 — pull request #1285 by phkelley (2013-01-27 22:32:36+00:00)
Title: Vector improvements and their fallout

I recently spent some time looking for improvements that could be made in vector.h/vector.c and this is what I came up with.

1. Some callers of `git_vector_*` functions were found to not be checking return values. The changes to check these return values are in commit.c, diff_tform.c, and remote.c.

2. The `git_vector` search functions (both linear and binary) were found to be using the return value of type "int" to encode both success/failure of the search as well as the index where the key was located. I modified these functions to return either 0 or GIT_ENOTFOUND as an int, and to take in a `size_t` pointer where the index is optionally written. The work to change these functions and their callers, all the way through the stack, constitutes the bulk of the changes in this PR, and it resulted in two changes to public API signatures -- for `git_index_find`, and `git_index_reuc_find`.

3. I'm not sure why `git__bsearch` (in util.c) was using an `unsigned int` instead of a `size_t` for its work. I went back and looked at the BSD implementation that our bsearch is based on, and that one looks to be using a `size_t`, so I'm fairly satisfied that we don't lose correctness by changing the type of this local variable to `size_t`.

4. In vector.c, I changed the implementation of `resize_vector` to be much more cautious. We carefully check for overflow, for example, when turning the desired number of elements in the array into the number of bytes to request from the allocator (by multiplying by `sizeof(void *)`). If the call to `git_realloc` fails, we make sure the vector is left in an unchanged state -- `realloc` supports this semantic. (While the overflow check appears to be doing a divide, the compiler is smart enough to know that if `sizeof(void *)` is 8, then dividing by 8 can be done using a right bit-shift of 3.)

5. I changed the vector resize factor from 1.75 to 1.5. The reason for doing this is to get the resize factor value to be lower than the golden ratio (1.618...). You can read online about why the STL uses this value -- the argument seemed persuasive to me. While here I also stopped using the syntax `existing_size * factor` to compute the new size. Since 1.5 is also 3 divided by 2, it's better to write `* 3 / 2`, which will be emitted by the compiler as `lea eax, [eax*2]` followed by a `shr` instead of going to x87 or MMX (which I think is required because the dot in the literal implies IEEE 754 semantics?). If we want to keep 1.75 for some reason, then we can still keep the speedup of using integer instructions, since 1.75 is 7 over 4 and the same tricks apply.

6. Various other minor tweaks in vector.c that don't seem to warrant much discussion. (If you feel differently please speak up!)

I think #2 above is probably the most controversial, probably because it introduces an API break. I'm all ears if people have opinions on this (extremely boring) subject matter.