Re: [PATCH v3 0/21] pack bitmaps
On 14/11/13 23:09, Ramsay Jones wrote: On 14/11/13 21:33, Jeff King wrote: On Thu, Nov 14, 2013 at 07:19:38PM +, Ramsay Jones wrote: Unfortunately, I didn't find time this weekend to finish the msvc build fixes. However, after a quick squint at these patches, I think you have almost done it for me! :-D I must have misunderstood the previous discussion, because my patch was written on the assumption that the ewah directory wouldn't be git-ified (e.g. #include git-compat-util.h). I think it was up for debate at some point, but we did decide to go ahead and git-ify. Please feel free to submit further fixups if you need them. Yep, will do; at present it looks like that one-liner. Despite saying I would wait for these patches to land in pu, I applied these patches to the next branch (@ 8721652 Sync with 1.8.5-rc2) so that I could try them out. As expected, everything was fine on Linux and cygwin, and the msvc build needed a one-liner fix. However, I didn't expect that MinGW would need the same fix! ;-) I had forgotten that git-compat-util.h does not include the inttypes.h header on MinGW (my previous patch included that header directly), so that we have to add the printf format macros directly to the compat/mingw.h header. [I assume that an earlier version of the library on MinGW did not have the inttypes.h and stdint.h headers. We could now include that header on MinGW and move the PRIuMAX, PRId64 and PRIx64 macros to compat/msvc.h, but I didn't think it was worth the churn ... ] The one-liner is given below ... ATB, Ramsay Jones -- 8 -- Subject: [PATCH] compat/mingw.h: Fix the MinGW and msvc builds Signed-off-by: Ramsay Jones ram...@ramsay1.demon.co.uk --- compat/mingw.h | 1 + 1 file changed, 1 insertion(+) diff --git a/compat/mingw.h b/compat/mingw.h index 92cd728..8828ede 100644 --- a/compat/mingw.h +++ b/compat/mingw.h @@ -345,6 +345,7 @@ static inline char *mingw_find_last_dir_sep(const char *path) #define PATH_SEP ';' #define PRIuMAX I64u #define PRId64 I64d +#define PRIx64 I64x void mingw_open_html(const char *path); #define open_html mingw_open_html -- 1.8.4 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v3 0/21] pack bitmaps
Jeff King p...@peff.net writes: - the ewah code used gcc's __builtin_ctzll, but did not provide a suitable fallback. We now provide a fallback in C. I was messing around with several implementations (including the use of msvc compiler intrinsics) with the intention of doing some timing tests etc. [I suspected my C fallback function (a different implementation to yours) would be slightly faster.] Yeah, I looked around for several implementations, and ultimately wrote one that was the most readable to me. The one I found shortest and most inscrutable was: return popcount((x -x) - 1); In two's complement, -x = ~x + 1 [1]. If you have a bunch of 0s at the end, as in (binary; a=~A etc) x = abcdef1000 then ~x = ABCDEF0111 ~x + 1 = -x = ABCDEF1000 (x-x) = 001000 (x-x) - 1 = 000111 popcount() of that is the number of trailing zeroes you started with. Please don't ask me to work out what happens in border cases; my head hurts already. [1] because x + ~x is all one bits. +1 makes it overflow to 0, so that x + -x = 0 as it should. -- Thomas Rast t...@thomasrast.ch -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH v3 0/21] pack bitmaps
Here's another iteration of the pack bitmaps series. Compared to v2, it changes: - misc style/typo fixes - portability fixes from Ramsay and Torsten - count-objects garbage-reporting patch from Duy - disable bitmaps when is_repository_shallow(); this also covers the case where the client is shallow, since we feed pack-objects a --shallow-file in that case. This used to done by checking !internal_rev_list, but that doesn't apply after cdab485. - ewah sources now properly use git-compat-util.h and do not include system headers - the ewah code uses ewah_malloc, ewah_realloc, and so forth to let the project use a particular allocator (and we want to use xmalloc and friends). And we defined those in pack-bitmap.h, but of course that had no effect on the ewah/*.c files that did not include pack-bitmap.h. Since we are hacking up and git-ifying libewok anyway, we can just set the hardcoded fallback to xmalloc instead of malloc. - the ewah code used gcc's __builtin_ctzll, but did not provide a suitable fallback. We now provide a fallback in C. - The bitmap reading code only handles a single bitmapped pack (since they must be fully closed, there is not much point in having multiple). It used to silently ignore extra bitmap indices it found, but will now warn that they are being ignored. - The name-hash cache is now optional, controlled by pack.writeBitmapHashCache. - The test script will now do basic interoperability testing with jgit (if you have jgit in your $PATH). - There are now perf tests. Spoiler alert: bitmaps make clones faster. See patch 20 for details. We can also measure the speedup from the hash cache (see patch 21). Not addressed: - I did not include the NEEDS_ALIGNED_ACCESS patch. I note that we do not even have a Makefile knob for this, and the code in read-cache.c has probably never actually been used. Are there real systems that have a problem? The read-cache code was in support of the index v4 experiment, which did away with the 8-byte padding. So it could be that we simply don't see it, because everything is currently aligned. - On a related note, we do some cast-buffer-to-struct magic on the mmap'd file. I note that the regular packfile reader also does this. How careful do we want to be? - We still assume that reusing a slice from the front of the pack will never miss delta bases. This is the case currently for packs generated by both git and JGit, but it would be nice to mark the property in the bitmap index. Adding a new flag would break JGit compatibility, though. We can either make it an option, or assume it's good enough for now and worry about it in v2. [01/21]: sha1write: make buffer const-correct [02/21]: revindex: Export new APIs [03/21]: pack-objects: Refactor the packing list [04/21]: pack-objects: factor out name_hash [05/21]: revision: allow setting custom limiter function [06/21]: sha1_file: export `git_open_noatime` [07/21]: compat: add endianness helpers [08/21]: ewah: compressed bitmap implementation [09/21]: documentation: add documentation for the bitmap format [10/21]: pack-bitmap: add support for bitmap indexes [11/21]: pack-objects: use bitmaps when packing objects [12/21]: rev-list: add bitmap mode to speed up object lists [13/21]: pack-objects: implement bitmap writing [14/21]: repack: stop using magic number for ARRAY_SIZE(exts) [15/21]: repack: turn exts array into array-of-struct [16/21]: repack: handle optional files created by pack-objects [17/21]: repack: consider bitmaps when performing repacks [18/21]: count-objects: recognize .bitmap in garbage-checking [19/21]: t: add basic bitmap functionality tests [20/21]: t/perf: add tests for pack bitmaps [21/21]: pack-bitmap: implement optional name_hash cache -Peff -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v3 0/21] pack bitmaps
On 14/11/13 12:41, Jeff King wrote: Here's another iteration of the pack bitmaps series. Compared to v2, it changes: - misc style/typo fixes - portability fixes from Ramsay and Torsten Unfortunately, I didn't find time this weekend to finish the msvc build fixes. However, after a quick squint at these patches, I think you have almost done it for me! :-D I must have misunderstood the previous discussion, because my patch was written on the assumption that the ewah directory wouldn't be git-ified (e.g. #include git-compat-util.h). So, most of my patch is no longer necessary, given the use of the git compat header (and removal of system headers). I suspect that you only need to add an '#define PRIx64 I64x' definition (Hmm, probably to the compat/mingw.h header). I won't know for sure until I actually try them out, of course. I will wait until these patches land in pu. [Note: the msvc build is still broken, but the failure is not caused by these patches. Unfortunately, the tests in t5310-*.sh fail. However, if I include some debug code, the tests pass ... :-P ] The part of the patch I was still working on was ... - count-objects garbage-reporting patch from Duy - disable bitmaps when is_repository_shallow(); this also covers the case where the client is shallow, since we feed pack-objects a --shallow-file in that case. This used to done by checking !internal_rev_list, but that doesn't apply after cdab485. - ewah sources now properly use git-compat-util.h and do not include system headers - the ewah code uses ewah_malloc, ewah_realloc, and so forth to let the project use a particular allocator (and we want to use xmalloc and friends). And we defined those in pack-bitmap.h, but of course that had no effect on the ewah/*.c files that did not include pack-bitmap.h. Since we are hacking up and git-ifying libewok anyway, we can just set the hardcoded fallback to xmalloc instead of malloc. - the ewah code used gcc's __builtin_ctzll, but did not provide a suitable fallback. We now provide a fallback in C. ... here. I was messing around with several implementations (including the use of msvc compiler intrinsics) with the intention of doing some timing tests etc. [I suspected my C fallback function (a different implementation to yours) would be slightly faster.] ATB, Ramsay Jones -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v3 0/21] pack bitmaps
On Thu, Nov 14, 2013 at 07:19:38PM +, Ramsay Jones wrote: Unfortunately, I didn't find time this weekend to finish the msvc build fixes. However, after a quick squint at these patches, I think you have almost done it for me! :-D I must have misunderstood the previous discussion, because my patch was written on the assumption that the ewah directory wouldn't be git-ified (e.g. #include git-compat-util.h). I think it was up for debate at some point, but we did decide to go ahead and git-ify. Please feel free to submit further fixups if you need them. - the ewah code used gcc's __builtin_ctzll, but did not provide a suitable fallback. We now provide a fallback in C. ... here. I was messing around with several implementations (including the use of msvc compiler intrinsics) with the intention of doing some timing tests etc. [I suspected my C fallback function (a different implementation to yours) would be slightly faster.] Yeah, I looked around for several implementations, and ultimately wrote one that was the most readable to me. The one I found shortest and most inscrutable was: return popcount((x -x) - 1); the details of which I still haven't worked through in my head. ;) I do think on most platforms that intrinsics or inline assembler are the way to go. My main goal was to get something correct that would let it compile everywhere, and then people can use that as a base for optimizing. Patches welcome. :) -Peff -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v3 0/21] pack bitmaps
On 14/11/13 21:33, Jeff King wrote: On Thu, Nov 14, 2013 at 07:19:38PM +, Ramsay Jones wrote: Unfortunately, I didn't find time this weekend to finish the msvc build fixes. However, after a quick squint at these patches, I think you have almost done it for me! :-D I must have misunderstood the previous discussion, because my patch was written on the assumption that the ewah directory wouldn't be git-ified (e.g. #include git-compat-util.h). I think it was up for debate at some point, but we did decide to go ahead and git-ify. Please feel free to submit further fixups if you need them. Yep, will do; at present it looks like that one-liner. - the ewah code used gcc's __builtin_ctzll, but did not provide a suitable fallback. We now provide a fallback in C. ... here. I was messing around with several implementations (including the use of msvc compiler intrinsics) with the intention of doing some timing tests etc. [I suspected my C fallback function (a different implementation to yours) would be slightly faster.] Yeah, I looked around for several implementations, and ultimately wrote one that was the most readable to me. The one I found shortest and most inscrutable was: return popcount((x -x) - 1); the details of which I still haven't worked through in my head. ;) Yeah, I stumbled over that one too! I do think on most platforms that intrinsics or inline assembler are the way to go. My main goal was to get something correct that would let it compile everywhere, and then people can use that as a base for optimizing. Patches welcome. :) Indeed, I can happily leave that to another day (or to someone else more motivated ;-) ATB, Ramsay Jones -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
