From: Junio C Hamano <hidden> Date: 2016-06-15 22:54:23
Nguyen Thai Ngoc Duy [off-list ref] writes:
The above output is done with "git diff --manual-rename=foo A B"
and "foo" contains (probably not in the best format though)
-- 8< --
attr.c dir.c
dir.c attr.c
-- 8< --
...
Comments?
It is a good direction to go in, I would think, to give users a way
to explicitly tell that "in comparison between these two trees, I
know path B in the postimage corresponds to path A in the preimage".
I however wonder why you did this as a separate function that only
does the explicitly marked ones. Probably it was easier as a POC to
do it this way, and that is fine.
The real version should do this in the same diffcore_rename()
function, by excluding the paths that the user explicitly told you
about from the the automatic matching logic, and instead matching
them up manually; then you can let the remainder of the paths be
paired by the existing code.
Notice how the non-nullness of rename_dst[i].pair is used as a cue
to skip the similarity computation in the expensive matrix part of
diffcore_rename()? That comes from find_exact_renames() that is
called earlier in the function. I would imagine that your logic
would fit _before_ we call find_exact_renames() as a call to a new
helper function (e.g. "record_explicit_renames()" perhaps).
Anything that reduces the cost in the matrix part should come
earlier, as that reduces the number of pairs we would need to try
matching up.
We might want to introduce a way to express the similarity score for
such a filepair that was manually constructed when showing the
result, though.
From: Jeff King <hidden> Date: 2016-06-15 22:54:23
On Tue, Jul 31, 2012 at 09:32:49AM -0700, Junio C Hamano wrote:
Nguyen Thai Ngoc Duy [off-list ref] writes:
quoted
The above output is done with "git diff --manual-rename=foo A B"
and "foo" contains (probably not in the best format though)
-- 8< --
attr.c dir.c
dir.c attr.c
-- 8< --
...
Comments?
It is a good direction to go in, I would think, to give users a way
to explicitly tell that "in comparison between these two trees, I
know path B in the postimage corresponds to path A in the preimage".
I do not think that is the right direction. Let's imagine that I have a
commit "A" and I annotate it (via notes or whatever) to say "between
A^^{tree} and A^{tree}, foo.c became bar.c". That will help me when
doing "git show" or "git log". But it will not help me when I later try
to merge "A" (or its descendent). In that case, I will compute the diff
between "A" and the merge-base (or worse, some descendent of "A" and the
merge-base), and I will miss this hint entirely.
A much better hint is to annotate pairs of sha1s, to say "do not bother
doing inexact rename correlation on this pair; I promise that they have
value N". Then it will find that pair no matter which trees or commits
are being diffed, and it will do so relatively inexpensively[1].
That is not fool-proof, of course. You might have a manual rename from
sha1 X to sha1 Y, and then a slight modification to Y to make Z. So you
would want some kind of transitivity to notice that X and Z correlate.
I think you could model it as a graph problem; sha1s are nodes, and each
"this is a rename" pair of annotated sha1s has an edge between them.
They are the "same file" if there is a path.
Of course that gives you bizarre and counter-intuitive results, because
X and Z might not actually be that similar. And that is why we have
rename detection in the first place. The idea of file identity (which
this fundamentally is) leads to these sorts of weird results.
I'm sure you could get better results by weakening the transitivity
according to the rename score, or something like that. But now you are
getting pretty complex.
-Peff
[1] We could actually cache rename results by storing pairs of sha1s
along with their rename score, and should be able to get a good
speedup (we are still src*dst in comparing, but now the comparison
is a simple table lookup rather than loading the blobs and computing
the differences). If we had such a cache, then manually marking a
rename would just be a matter of priming the cache with your manual
entries.
On Wed, Aug 1, 2012 at 2:23 AM, Jeff King [off-list ref] wrote:
quoted
It is a good direction to go in, I would think, to give users a way
to explicitly tell that "in comparison between these two trees, I
know path B in the postimage corresponds to path A in the preimage".
I do not think that is the right direction. Let's imagine that I have a
commit "A" and I annotate it (via notes or whatever) to say "between
A^^{tree} and A^{tree}, foo.c became bar.c". That will help me when
doing "git show" or "git log". But it will not help me when I later try
to merge "A" (or its descendent). In that case, I will compute the diff
between "A" and the merge-base (or worse, some descendent of "A" and the
merge-base), and I will miss this hint entirely.
A much better hint is to annotate pairs of sha1s, to say "do not bother
doing inexact rename correlation on this pair; I promise that they have
value N".
I haven't had time to think it through yet but I throw my thoughts in
any way. I actually went with your approach first. But it's more
difficult to control the renaming. Assume we want to tell git to
rename SHA-1 "A" to SHA-1 "B". What happens if we have two As in the
source tree and two Bs in the target tree? What happens if two As and
one B, or one A and two Bs? What if a user defines A -> B and A -> C,
and we happen to have two As in source tree and B and C in target
tree?
There's also the problem with transferring this information. With
git-notes I think I can transfer it (though not automatically). How do
we transfer sha1 map (that you mentioned in the commit generation mail
in this thread)?
Then it will find that pair no matter which trees or commits
are being diffed, and it will do so relatively inexpensively[1].
But does that happen often in practice? I mean diff-ing two arbitrary
trees and expect rename correction. I disregarded it as "git log" is
my main case, but I'm just a single user..
--
Duy
From: Jeff King <hidden> Date: 2016-06-15 22:54:24
On Wed, Aug 01, 2012 at 08:10:12AM +0700, Nguyen Thai Ngoc Duy wrote:
quoted
I do not think that is the right direction. Let's imagine that I have a
commit "A" and I annotate it (via notes or whatever) to say "between
A^^{tree} and A^{tree}, foo.c became bar.c". That will help me when
doing "git show" or "git log". But it will not help me when I later try
to merge "A" (or its descendent). In that case, I will compute the diff
between "A" and the merge-base (or worse, some descendent of "A" and the
merge-base), and I will miss this hint entirely.
A much better hint is to annotate pairs of sha1s, to say "do not bother
doing inexact rename correlation on this pair; I promise that they have
value N".
I haven't had time to think it through yet but I throw my thoughts in
any way. I actually went with your approach first. But it's more
difficult to control the renaming. Assume we want to tell git to
rename SHA-1 "A" to SHA-1 "B". What happens if we have two As in the
source tree and two Bs in the target tree? What happens if two As and
one B, or one A and two Bs? What if a user defines A -> B and A -> C,
and we happen to have two As in source tree and B and C in target
tree?
Yes, it disregards path totally. But if you had the exact same movement
of content from one path to another in one instance, and it is
considered a rename, wouldn't it also be a rename in a second instance?
There's also the problem with transferring this information. With
git-notes I think I can transfer it (though not automatically). How do
we transfer sha1 map (that you mentioned in the commit generation mail
in this thread)?
That is orthogonal to the issue of what is being stored. I chose my
mmap'd disk implementation because it is very fast, which makes it nice
for a performance cache. But you could store the same thing in git-notes
(indexed by dst sha1, I guess, and then pointing to a blob of (src,
score) pairs.
If you want to include path-based hints in a commit, I'd say that using
some micro-format in the commit message would be the simplest thing. But
that has been discussed before; ultimately the problem is that it only
covers _one_ diff that we do with that commit (it is probably the most
common, of course, but it doesn't cover them all).
quoted
Then it will find that pair no matter which trees or commits
are being diffed, and it will do so relatively inexpensively[1].
But does that happen often in practice? I mean diff-ing two arbitrary
trees and expect rename correction. I disregarded it as "git log" is
my main case, but I'm just a single user..
It happens every time merge-recursive does rename detection, which
includes "git merge" but also things like "cherry-pick".
-Peff
On Wed, Aug 1, 2012 at 9:01 AM, Jeff King [off-list ref] wrote:
On Wed, Aug 01, 2012 at 08:10:12AM +0700, Nguyen Thai Ngoc Duy wrote:
quoted
quoted
I do not think that is the right direction. Let's imagine that I have a
commit "A" and I annotate it (via notes or whatever) to say "between
A^^{tree} and A^{tree}, foo.c became bar.c". That will help me when
doing "git show" or "git log". But it will not help me when I later try
to merge "A" (or its descendent). In that case, I will compute the diff
between "A" and the merge-base (or worse, some descendent of "A" and the
merge-base), and I will miss this hint entirely.
A much better hint is to annotate pairs of sha1s, to say "do not bother
doing inexact rename correlation on this pair; I promise that they have
value N".
I haven't had time to think it through yet but I throw my thoughts in
any way. I actually went with your approach first. But it's more
difficult to control the renaming. Assume we want to tell git to
rename SHA-1 "A" to SHA-1 "B". What happens if we have two As in the
source tree and two Bs in the target tree? What happens if two As and
one B, or one A and two Bs? What if a user defines A -> B and A -> C,
and we happen to have two As in source tree and B and C in target
tree?
Yes, it disregards path totally. But if you had the exact same movement
of content from one path to another in one instance, and it is
considered a rename, wouldn't it also be a rename in a second instance?
Yes. This is probably cosmetics only, but without path information, we
leave it to chance to decide which A to pair with B and C (in the
A->B, A->C case above). Wrong path might lead to funny effects (i'm
thinking of git log --follow).
quoted
There's also the problem with transferring this information. With
git-notes I think I can transfer it (though not automatically). How do
we transfer sha1 map (that you mentioned in the commit generation mail
in this thread)?
I wasn't clear. This is about transferring info across repositories.
That is orthogonal to the issue of what is being stored. I chose my
mmap'd disk implementation because it is very fast, which makes it nice
for a performance cache. But you could store the same thing in git-notes
(indexed by dst sha1, I guess, and then pointing to a blob of (src,
score) pairs.
If you want to include path-based hints in a commit, I'd say that using
some micro-format in the commit message would be the simplest thing.
Rename correction is after the commit is created. I don't think we can
recreate commits.
But
that has been discussed before; ultimately the problem is that it only
covers _one_ diff that we do with that commit (it is probably the most
common, of course, but it doesn't cover them all).
How about we generate sha1 mapping from commit hints? We try to take
advantage of path hints when we can. Else we fall back to sha-1
mapping. This way we can transfer commit hints as git-notes to another
repo, then regenerate sha-1 mapping there. No need to transfer sha1
maps.
quoted
quoted
Then it will find that pair no matter which trees or commits
are being diffed, and it will do so relatively inexpensively[1].
But does that happen often in practice? I mean diff-ing two arbitrary
trees and expect rename correction. I disregarded it as "git log" is
my main case, but I'm just a single user..
It happens every time merge-recursive does rename detection, which
includes "git merge" but also things like "cherry-pick".
From: Jeff King <hidden> Date: 2016-06-15 22:54:24
On Wed, Aug 01, 2012 at 11:36:00AM +0700, Nguyen Thai Ngoc Duy wrote:
quoted
That is orthogonal to the issue of what is being stored. I chose my
mmap'd disk implementation because it is very fast, which makes it nice
for a performance cache. But you could store the same thing in git-notes
(indexed by dst sha1, I guess, and then pointing to a blob of (src,
score) pairs.
If you want to include path-based hints in a commit, I'd say that using
some micro-format in the commit message would be the simplest thing.
Rename correction is after the commit is created. I don't think we can
recreate commits.
Yes, if you go with a commit-based approach, you can do either notes or
in-commit messages. In other words, I would break the solutions down as:
1. Store sha1+sha1 -> score mapping (i.e., what I suggested). This is
fundamentally a global store, not a per-commit store. For storage,
you can do one (or a combination) of:
a. Store the mapping in some local file. Fast, but can't be shared.
b. Store the mapping in a note (probably indexed by the destination
blob sha1). Less efficient, but easy to share.
2. Store path -> path mapping. This is fundamentally a per-commit
store, since it is valid only in the diff between two particular
trees. For storage, you can do one (or a combination) of:
a. Store the mapping inside the commit object. Simple to share, but
hard to change later.
b. Store it in a note indexed by the commit object. Slightly harder
to share, but can change later.
I implemented (1a). Implementing (1b) would be easy, but for a full-on
cache (especially for "-C"), I think the resulting size might be
prohibitive.
All solutions under (2) suffer from the same problem: they are accurate
only for a single diff. For other diffs, you would either have to not
use the feature, or you would be stuck traversing the history and
assigning a temporary file identity (e.g., given commits A->B->C, and in
A->B we rename "foo" to "bar", the diff between A and C could discover
that A's "foo" corresponds to C's "bar").
That is slower than what we do now, but that is only one problem with
it. Another is that the history relationship between the commits might
be complex. In the example above, we had a direct-descendent
relationship. But what about one with branching, and one side does the
rename and the other does not? Or even cherry-picking from an unrelated
part of history entirely?
And I think all forms of (2) will suffer from this, no matter how you
store the data. The reason I mentioned specifically putting it in the
commit message (i.e., 2a) because that is what people suggested in the
very early days of git (e.g., saying that rename detection is OK, but
could we supplement it with hints at commit-time?). And all of the
arguments against it back then apply equally now. And apply equally to
storing it in notes, because it is just another form of the same thing.
quoted
But that has been discussed before; ultimately the problem is that
it only covers _one_ diff that we do with that commit (it is
probably the most common, of course, but it doesn't cover them all).
How about we generate sha1 mapping from commit hints? We try to take
advantage of path hints when we can. Else we fall back to sha-1
mapping. This way we can transfer commit hints as git-notes to another
repo, then regenerate sha-1 mapping there. No need to transfer sha1
maps.
Yes. You could definitely pre-seed the sha1 mapping from the per-commit
hints. However, if you are interested in overriding git's rename
detection, then per-commit hints will only let you do part of what you
want. For example, consider a linear history like this:
A--B--C
And imagine that commit B renamed a file from "foo" to "bar", and that
commit C further modified "bar". Let's say that git did not detect the
rename in B, but you manually annotated it. As a result, we seed the
sha1 mapping to show that the sha1 of A:foo and the sha1 of B:bar has a
rename score of 100%.
Now I want to do a diff between A and C (e.g., for rename detection on
one side of a merge). But their sha1s are not in my mapping (because
C:bar is not the same as B:bar), and I don't find the rename. To find
it, I cannot seed a per-commit path mapping. I must seed the sha1
mapping itself.
So to adapt your per-commit mapping into a sha1 mapping, the seeding
process would have to actually walk the history, transitively creating
sha1 mapping entries (i.e., seeing that "bar" changed between B and C,
and therefore mapping A:foo to C:bar, as well).
For this reason, I'm not sure that stored overrides like this are
generally useful in the long run. I think storage is useful for
_caching_ the results, because it doesn't have to be perfect; it just
helps with some repetitive queries. Whereas for overriding, I think it
is much more interesting to override _particular_ diff. E.g., to say "I
am merging X and Y, and please pretend that Y renamed "foo" to "bar"
when you do rename detection.
And in that sense, your "git log" example can be considered a
special-case of this: you are saying that the diff from $commit to
$commit^ is done frequently, so rather than saying "please pretend..."
each time, you would like to store the information forever. And storing
it in the commit message or a note is one way of doing that.
I don't think there's anything fundamentally _wrong_ with that, but I
kind of question its usefulness. In other words, what is the point in
doing so? If it is inform the user that semantically the commit did a
rename, even though the content changed enough that rename detection
does not find it, then I would argue that you should simply state it in
the commit message (or in a human-readable git-note, if it was only
realized after the fact).
But there is not much point in making it machine-readable, since the
interesting machine-readable things we do with renames are:
1. Show the diff against the rename src, which can often be easier to
read. Except that if rename detection did not find it, it is
probably _not_ going to be easier to read.
2. Applying content to the destination of a merge. But you're almost
never doing the diff between a commit and its parent, so the
information would be useless.
-Peff
On Thu, Aug 2, 2012 at 4:27 AM, Jeff King [off-list ref] wrote:
Yes, if you go with a commit-based approach, you can do either notes or
in-commit messages. In other words, I would break the solutions down as:
1. Store sha1+sha1 -> score mapping (i.e., what I suggested). This is
fundamentally a global store, not a per-commit store. For storage,
you can do one (or a combination) of:
a. Store the mapping in some local file. Fast, but can't be shared.
b. Store the mapping in a note (probably indexed by the destination
blob sha1). Less efficient, but easy to share.
I implemented (1a). Implementing (1b) would be easy, but for a full-on
cache (especially for "-C"), I think the resulting size might be
prohibitive.
(1a) is good regardless rename overrides. Why don't you polish and
submit it? We can set some criteria to limit the cache size while
keeping computation reasonably low. Caching rename scores for file
pairs that has file size larger than a limit is one. Rename matrix
size could also be a candidate. We could even cache just rename scores
for recent commits (i.e. close to heads) only with the assumption that
people diff/apply recent commits more often.
All solutions under (2) suffer from the same problem: they are accurate
only for a single diff. For other diffs, you would either have to not
use the feature, or you would be stuck traversing the history and
assigning a temporary file identity (e.g., given commits A->B->C, and in
A->B we rename "foo" to "bar", the diff between A and C could discover
that A's "foo" corresponds to C's "bar").
Yeah. If we go with manual overrides, I expect users to deal with
these manually too. IOW they'll need to create a mapping for A->C
themselves. We can help detect that there are manual overrides in some
cases, like merge, and let users know that manual overrides are
ignored. For merge, I think we can just check for all commits while
traversing looking for bases.
For this reason, I'm not sure that stored overrides like this are
generally useful in the long run. I think storage is useful for
_caching_ the results, because it doesn't have to be perfect; it just
helps with some repetitive queries. Whereas for overriding, I think it
is much more interesting to override _particular_ diff. E.g., to say "I
am merging X and Y, and please pretend that Y renamed "foo" to "bar"
when you do rename detection.
And in that sense, your "git log" example can be considered a
special-case of this: you are saying that the diff from $commit to
$commit^ is done frequently, so rather than saying "please pretend..."
each time, you would like to store the information forever. And storing
it in the commit message or a note is one way of doing that.
Yep, specifying rename overrides between two trees is probably better.
I don't think there's anything fundamentally _wrong_ with that, but I
kind of question its usefulness. In other words, what is the point in
doing so? If it is inform the user that semantically the commit did a
rename, even though the content changed enough that rename detection
does not find it, then I would argue that you should simply state it in
the commit message (or in a human-readable git-note, if it was only
realized after the fact).
But there is not much point in making it machine-readable, since the
interesting machine-readable things we do with renames are:
1. Show the diff against the rename src, which can often be easier to
read. Except that if rename detection did not find it, it is
probably _not_ going to be easier to read.
Probably. Still it helps "git log --follow" to follow the correct
track in the 1% case that rename detection does go wrong.
2. Applying content to the destination of a merge. But you're almost
never doing the diff between a commit and its parent, so the
information would be useless.
Having a way to interfere rename detection, even manually, could be
good in this case if it reduces conflicts. We could feed rename
overrides using command line.
--
Duy
From: Jeff King <hidden> Date: 2016-06-15 22:54:24
On Thu, Aug 02, 2012 at 07:08:25PM +0700, Nguyen Thai Ngoc Duy wrote:
quoted
I implemented (1a). Implementing (1b) would be easy, but for a full-on
cache (especially for "-C"), I think the resulting size might be
prohibitive.
(1a) is good regardless rename overrides. Why don't you polish and
submit it? We can set some criteria to limit the cache size while
keeping computation reasonably low. Caching rename scores for file
pairs that has file size larger than a limit is one. Rename matrix
size could also be a candidate. We could even cache just rename scores
for recent commits (i.e. close to heads) only with the assumption that
people diff/apply recent commits more often.
I'll polish and share it. I'm still not 100% sure it's a good idea,
because introducing an on-disk cache means we need to _manage_ that
cache. How big will it be? Who will prune it when it gets too big? By
what criteria? And so on.
But if it's all hidden behind a config option, then it won't hurt people
who don't use it. And people who do use it can gather data on how the
caches grow.
quoted
All solutions under (2) suffer from the same problem: they are accurate
only for a single diff. For other diffs, you would either have to not
use the feature, or you would be stuck traversing the history and
assigning a temporary file identity (e.g., given commits A->B->C, and in
A->B we rename "foo" to "bar", the diff between A and C could discover
that A's "foo" corresponds to C's "bar").
Yeah. If we go with manual overrides, I expect users to deal with
these manually too. IOW they'll need to create a mapping for A->C
themselves. We can help detect that there are manual overrides in some
cases, like merge, and let users know that manual overrides are
ignored. For merge, I think we can just check for all commits while
traversing looking for bases.
Yeah, merges are a special case, in that we know the diff we perform
will always have a direct-ancestor relationship (since it is always
between a tip and the merge base).
quoted
But there is not much point in making it machine-readable, since the
interesting machine-readable things we do with renames are:
1. Show the diff against the rename src, which can often be easier to
read. Except that if rename detection did not find it, it is
probably _not_ going to be easier to read.
Probably. Still it helps "git log --follow" to follow the correct
track in the 1% case that rename detection does go wrong.
Thanks. I didn't think of --follow, but that is a good counterpoint to
my argument.
quoted
2. Applying content to the destination of a merge. But you're almost
never doing the diff between a commit and its parent, so the
information would be useless.
Having a way to interfere rename detection, even manually, could be
good in this case if it reduces conflicts. We could feed rename
overrides using command line.
Yeah. I think I'd start with letting you feed pairs to diff_options,
give it a command-line option to see how useful it is, and then later on
consider a mechanism for extracting those pairs automatically from
commits or notes.
-Peff
From: Jeff King <hidden> Date: 2016-06-15 22:54:25
On Thu, Aug 02, 2012 at 06:41:55PM -0400, Jeff King wrote:
quoted
(1a) is good regardless rename overrides. Why don't you polish and
submit it? We can set some criteria to limit the cache size while
keeping computation reasonably low. Caching rename scores for file
pairs that has file size larger than a limit is one. Rename matrix
size could also be a candidate. We could even cache just rename scores
for recent commits (i.e. close to heads) only with the assumption that
people diff/apply recent commits more often.
I'll polish and share it. I'm still not 100% sure it's a good idea,
because introducing an on-disk cache means we need to _manage_ that
cache. How big will it be? Who will prune it when it gets too big? By
what criteria? And so on.
But if it's all hidden behind a config option, then it won't hurt people
who don't use it. And people who do use it can gather data on how the
caches grow.
Here it is, all polished up. I'm still a little lukewarm on it for two
reasons:
1. The whole idea. For the reasons above, I'm a little iffy on doing
this cache at all. It does yield speedups, but only in some
specific cases. So it's hidden behind a diff.renamecaches option
and off by default.
2. The implementation is a little...gross. Long ago, I had written a
type-generic map class for git using void pointers. It ended up
complex and had problems with unaligned accesses. So I rewrote it
using preprocessor macro expansion (e.g., you'd call
IMPLEMENT_MAP(foo, const char *, int) or similar). But that wasn't
quite powerful enough, as I really want conditional compilation
inside the macro expansion, but you can't #ifdef.
So I really wanted some kind of code generation that could do
conditionals. Which you can do with the C preprocessor, but rather
than expanding macros, you have to #include templates that expand
based on parameters you've set. Which is kind of ugly and
non-intuitive, but it does work. Look at patch 1 to see what I
mean.
Also, this sort of pre-processor hackery to create type-generic
data structures is the first step on the road that eventually led
to C++ being developed. And that scares me a little.
So yeah. Here it is. I'm not sure yet if it's a good idea or not.
[1/8]: implement generic key/value map
Infrastructure.
[2/8]: map: add helper functions for objects as keys
[3/8]: fast-export: use object to uint32 map instead of "decorate"
[4/8]: decorate: use "map" for the underlying implementation
These ones are optional for this series, but since we are introducing
the infrastructure anyway (which is really just a generalized form of
what "decorate" does), it offsets the code bloat.
[5/8]: map: implement persistent maps
[6/8]: implement metadata cache subsystem
More infrastructure.
[7/8]: implement rename cache
[8/8]: diff: optionally use rename cache
And these are the actual rename cache.
-Peff
From: Jeff King <hidden> Date: 2016-06-15 22:54:25
It is frequently useful to have a fast, generic data
structure mapping keys to values. We already have something
like this in the "decorate" API, but it has two downsides:
1. The key type must always be a "struct object *".
2. The value type is a void pointer, which means it is
inefficient and cumbersome for storing small values.
One must either encode their value inside the void
pointer, or allocate additional storage for the pointer
to point to.
This patch introduces a generic map data structure, mapping
keys of arbitrary type to values of arbitrary type.
One possible strategy for implementation is to have a struct
that points to a sequence of bytes for each of the key and
the value, and to try to treat them as opaque in the code.
However, this code gets complex, has a lot of casts, and
runs afoul of violating alignment and strict aliasing rules.
This patch takes a different approach. We parameterize the
types in each map and putting the declarations and
implementations inside macros. This lets the compiler see
the actual code, with its real types, and figure out things
like struct packing and alignment itself.
Signed-off-by: Jeff King <redacted>
---
This is the one with the pre-processor grossness. Don't be _too_ scared
off by the ugliness of test-map.c; it's also trying to be polymorphic
with respect to different maps, which makes it even uglier. See patches
2 and 3 for a more reasonable application.
.gitignore | 1 +
Documentation/technical/api-map.txt | 214 ++++++++++++++++++++++++++++++++++++
Makefile | 5 +
map-decl.h | 22 ++++
map-done.h | 19 ++++
map-impl.h | 94 ++++++++++++++++
map-init.h | 24 ++++
t/t0007-map.sh | 50 +++++++++
test-map.c | 182 ++++++++++++++++++++++++++++++
9 files changed, 611 insertions(+)
create mode 100644 Documentation/technical/api-map.txt
create mode 100644 map-decl.h
create mode 100644 map-done.h
create mode 100644 map-impl.h
create mode 100644 map-init.h
create mode 100755 t/t0007-map.sh
create mode 100644 test-map.c
@@ -0,0 +1,214 @@+map API+=======++The map API is a system for efficiently mapping keys to values in memory. Items+are stored in a hash table for fast lookup; storage efficiency is achieved+through macro-based code generation, which lets the compiler store values+compactly in memory.++Due to the code generation, there are two different facets of this API: macros+to build new types of mappings (i.e., generate new function and struct+definitions), and generated functions to store and retrieve values from a+particular mapping.+++Related APIs+------------++The hash API provides a similar key/value store. However, it does not deal with+hash collisions itself, leaving the caller to handle bucket management (but+this is a feature if you are interested in using the collisions as part of an+algorithm). Furthermore, it can store only void pointers, making storage of+small values inefficient and cumbersome.++The decorate API provides a similar interface to map, but is restricted to+using "struct object" as the key, and a void pointer as the value.+++Defining New Map Types+----------------------++A map type is uniquely defined by the pair of its key and value types. To+define a new type, you must set up some preprocessor defines to specify+the key and values types, along with any special options for the+implementation. Then to instantiate the declaration of a map (i.e., the+bits that would go in a header file), include "map-decl.h". To+instantiate the implementation, include "map-impl.h". To clean up your+preprocessor options, include "map-done.h".++The following map defines are available:++`NAME`::++ Required. The name of the map. This should syntactically be a C+ identifier (alphanumeric and underscore), and should describe+ the types involved in the map (e.g., `object_uint32` to map+ objects to 32-bit integers).++`KEY_TYPE`::++ Required. The C type of the key, as it will be stored in the+ hash (e.g., `struct object *` to store an object pointer).++`PASS_KEY_BY_REF`::++ Optional. If defined, indicates that keys are a complex type+ that should be passed between functions using pointers.+ Otherwise, keys are passed by value.++`HASH`::++ Required. A function that will convert an object of type+ `KEY_TYPE` into an integer hash value.++`KEY_EQUAL`::++ Required. A function that will compare two keys, and return+ non-zero if and only if they are equal.++`VALUE_TYPE`::++ Required. The C type of the value, as it will be stored in the+ hash (e.g., `uint32_t` to store a 32-bit integer).++`SENTINEL_NULL`::++ Optional. If defined, indicates that keys can store an all-zero+ sentinel value (e.g., if the key is a pointer). This enables an+ optimization to shrink the size of each map entry, at the cost+ of not being able to store `NULL` key pointers in the map.+++Data Structures+---------------++Each defined map type will have its own structure (e.g., `map_object_uint32`).++`struct map_NAME`::++ A single map object. This struct should be initialized to all-zeroes.+ The `nr` field specifies the number of items stored in the map. The+ `size` field specifies the number of hash buckets allocated. The `hash`+ field stores the actual data. Callers should never need to look at+ these fields unless they are enumerating all elements of the map (see+ the example below).++`struct map_entry_NAME`::++ A single key/value entry in the hash, which may or may not+ contain valid data. If `SENTINEL_NULL` is defined, then an empty+ entry will have a NULL key; otherwise, there is a `used` field+ which will be zero in an empty entry (in which case the contents+ of the `key` field are undefined). If the entry is empty, the+ contents of the `value` field is undefined. You should never+ need to use this type directly, unless you are enumerating all+ elements of a map.+++Functions+---------++Each defined map type will have its own set of access functions (e.g.,+`map_get_object_uint32`).++`map_get_NAME(struct map_NAME *, KEY_TYPE key, VALUE_TYPE *value)`::++ Retrieve the value corresponding to `key`, returning it via the+ pointer `value`. Returns 1 if an item was found, zero otherwise+ (in which case `value` is unchanged). If `PASS_KEY_BY_REF` is+ defined, the key is passed in as a `const KEY_TYPE *`.++`map_set_NAME(struct map_NAME *, KEY_TYPE key, VALUE_TYPE value, VALUE_TYPE *old)`::++ Insert a mapping from `key` to `value`. If a mapping for `key`+ already existed, the previous value is copied into `old` (if it+ is non-NULL) and the function returns 1. Otherwise, the function+ returns 0. If `PASS_KEY_BY_REF` or `PASS_VALUE_BY_REF` is+ defined, the key and value are passed in as `const KEY_TYPE *`+ and `const VALUE_TYPE *`, respectively.+++Examples+--------++Declare a new mapping type of strings to integers:++-------------------------------------------------------------------+/* in map-string-int.h */+#define NAME string_int+#define KEY_TYPE const char *+#define VALUE_TYPE int+#include "map-decl.h"+#include "map-done.h"+-------------------------------------------------------------------++Implement the mapping:++-------------------------------------------------------------------+/* in map-string-int.c */++static unsigned int hash_string(const char * const *strp, unsigned int n)+{+ unsigned long hash = 0;+ const char *p;++ for (p = *strp; *p; p++)+ hash = (hash << 5) + *p;+ return hash % n;+}++static unsigned int string_equal(const char * const *a, const char * const *b)+{+ return !strcmp(*a, *b);+}++#define NAME string_int+#define KEY_TYPE const char *+#define VALUE_TYPE int+#include "map-impl.h"+#include "map-done.h"+-------------------------------------------------------------------++Store and retrieve integers by string (note that the map will not+duplicate the strings; the type is defined to merely store the+pointer values).++-------------------------------------------------------------------+#include "map-string-int.h"++static struct map_string_int foos;++void store_foo(const char *s, int foo)+{+ int old;+ if (map_set_object_int(&foos, xstrdup(s), foo, &old))+ printf("old value was %d\n", old);+}++void print_foo(const char *s)+{+ int v;++ if (map_get_object_int(&foos, s, &v))+ printf("foo: %d\n", v);+ else+ printf("no such foo\n");+}+-------------------------------------------------------------------++Iterate over all map entries:++-------------------------------------------------------------------+void dump_foos(void)+{+ int i;++ printf("there are %u foos:\n", foos.nr);++ for (i = 0; i < foos.size; i++) {+ struct map_entry_string_int *e = foos.hash + i;+ if (e->used)+ printf("%s -> %d\n", e->key, e->value);+ }+}+-------------------------------------------------------------------
@@ -0,0 +1,50 @@+#!/bin/sh++test_description='basic tests for the map implementation'+../test-lib.sh++test_expect_success'setup input''+cat>input<<-\EOF+f6+b2+a1+e5+i9+g7+d4+h8+c3+EOF+'++fortypeinpointerstruct;do+test_expect_success"look up elements ($type)""+cat>expect<<-\EOF&&+a:1+i:9+d:4+EOF+test-map$typefindaid<input>actual&&+test_cmpexpectactual+"++test_expect_success"iterate over elements ($type)""+cat>expect<<-\EOF&&+a:1+b:2+c:3+d:4+e:5+f:6+g:7+h:8+i:9+EOF+test-map$typeprint<input>actual&&+# iteration order is hash-dependent, so we must sort+sort<actual>actual.sorted&&+test_cmpexpectactual.sorted+"+done++test_done
From: Jeff King <hidden> Date: 2016-06-15 22:54:25
These functions can be used as HASH and KEY_EQUAL functions
when defining new maps with "struct object *" as their key.
Signed-off-by: Jeff King <redacted>
---
Makefile | 1 +
map-object.h | 19 +++++++++++++++++++
2 files changed, 20 insertions(+)
create mode 100644 map-object.h
From: Jeff King <hidden> Date: 2016-06-15 22:54:25
The decoration API maps objects to void pointers. This is a
subset of what the map API is capable of, so let's get rid
of the duplicate implementation.
We could just fix all callers of decorate to call the map
API directly. However, the map API is very generic since it
is meant to handle any type. In particular, it can't use
sentinel values like "NULL" to indicate "entry not found"
(since it doesn't know whether the type can represent such a
sentinel value), which makes the interface slightly more
complicated.
Instead, let's keep the existing decorate API as a wrapper
on top of map. No callers need to be updated at all.
Signed-off-by: Jeff King <redacted>
---
Documentation/technical/api-decorate.txt | 38 +++++++++++++-
Makefile | 3 ++
decorate.c | 85 +++-----------------------------
decorate.h | 10 ++--
map-object-void-params.h | 6 +++
map-object-void.c | 7 +++
map-object-void.h | 8 +++
7 files changed, 70 insertions(+), 87 deletions(-)
create mode 100644 map-object-void-params.h
create mode 100644 map-object-void.c
create mode 100644 map-object-void.h
@@ -1,6 +1,40 @@ decorate API ============-Talk about <decorate.h>+The decorate API is a system for efficiently mapping objects to values+in memory. It is slightly slower than an actual member of an object+struct (because it incurs a hash lookup), but it uses less memory when+the mapping is not in use, or when the number of decorated objects is+small compared to the total number of objects.-(Linus)+The decorate API is a special form of the `map` link:api-map.html[map+API]. It has slightly simpler calling conventions, but only use objects+as keys, and can only store void pointers as values.+++Data Structures+---------------++`struct decoration`::++ This structure represents a single mapping of objects to values.+ The `name` field is not used by the decorate API itself, but may+ be used by calling code. The `map` field represents the actual+ mapping of objects to void pointers (see the+ link:api-map.html[map API] for details).+++Functions+---------++`add_decoration`::++ Add a mapping from an object to a void pointer. If there was a+ previous value for this object, the function returns this value;+ otherwise, the function returns NULL.++`lookup_decoration`::++ Retrieve the stored value pointer for an object from the+ mapping. The return value is the value pointer, or `NULL` if+ there is no value for this object.
@@ -1,88 +1,17 @@-/*-*decorate.c-decorateagitobjectwithsomearbitrary-*data.-*/#include"cache.h"-#include"object.h"#include"decorate.h"-staticunsignedinthash_obj(conststructobject*obj,unsignedintn)-{-unsignedinthash;--memcpy(&hash,obj->sha1,sizeof(unsignedint));-returnhash%n;-}--staticvoid*insert_decoration(structdecoration*n,conststructobject*base,void*decoration)-{-intsize=n->size;-structobject_decoration*hash=n->hash;-unsignedintj=hash_obj(base,size);--while(hash[j].base){-if(hash[j].base==base){-void*old=hash[j].decoration;-hash[j].decoration=decoration;-returnold;-}-if(++j>=size)-j=0;-}-hash[j].base=base;-hash[j].decoration=decoration;-n->nr++;-returnNULL;-}--staticvoidgrow_decoration(structdecoration*n)-{-inti;-intold_size=n->size;-structobject_decoration*old_hash=n->hash;--n->size=(old_size+1000)*3/2;-n->hash=xcalloc(n->size,sizeof(structobject_decoration));-n->nr=0;--for(i=0;i<old_size;i++){-conststructobject*base=old_hash[i].base;-void*decoration=old_hash[i].decoration;--if(!base)-continue;-insert_decoration(n,base,decoration);-}-free(old_hash);-}--/* Add a decoration pointer, return any old one */void*add_decoration(structdecoration*n,conststructobject*obj,-void*decoration)+void*decoration){-intnr=n->nr+1;--if(nr>n->size*2/3)-grow_decoration(n);-returninsert_decoration(n,obj,decoration);+void*ret=NULL;+map_set_object_void(&n->map,obj,decoration,&ret);+returnret;}-/* Lookup a decoration pointer */void*lookup_decoration(structdecoration*n,conststructobject*obj){-unsignedintj;--/* nothing to lookup */-if(!n->size)-returnNULL;-j=hash_obj(obj,n->size);-for(;;){-structobject_decoration*ref=n->hash+j;-if(ref->base==obj)-returnref->decoration;-if(!ref->base)-returnNULL;-if(++j==n->size)-j=0;-}+void*ret=NULL;+map_get_object_void(&n->map,obj,&ret);+returnret;}
From: Jeff King <hidden> Date: 2016-06-15 22:54:25
Previously we encoded the "mark" mapping inside the "void *"
field of a "struct decorate". It's a little more natural for
us to do so using a data structure made for holding actual
values.
Signed-off-by: Jeff King <redacted>
---
builtin/fast-export.c | 46 +++++++++++++++++++++-------------------------
1 file changed, 21 insertions(+), 25 deletions(-)
@@ -75,20 +85,9 @@ static int has_unshown_parent(struct commit *commit)return0;}-/* Since intptr_t is C99, we do not use it here */-staticinlineuint32_t*mark_to_ptr(uint32_tmark)-{-return((uint32_t*)NULL)+mark;-}--staticinlineuint32_tptr_to_mark(void*mark)-{-return(uint32_t*)mark-(uint32_t*)NULL;-}-staticinlinevoidmark_object(structobject*object,uint32_tmark){-add_decoration(&idnums,object,mark_to_ptr(mark));+map_set_object_uint32(&idnums,object,mark,NULL);}staticinlinevoidmark_next_object(structobject*object)
@@ -567,15 +563,15 @@ static void export_marks(char *file)die_errno("Unable to open marks file %s for writing.",file);for(i=0;i<idnums.size;i++){-if(deco->base&&deco->base->type==1){-mark=ptr_to_mark(deco->decoration);-if(fprintf(f,":%"PRIu32" %s\n",mark,-sha1_to_hex(deco->base->sha1))<0){+conststructmap_entry_object_uint32*m=idnums.hash+i;++if(m->key&&m->key->type==1){+if(fprintf(f,":%"PRIu32" %s\n",m->value,+sha1_to_hex(m->key->sha1))<0){e=1;break;}}-deco++;}e|=ferror(f);
From: Jeff King <hidden> Date: 2016-06-15 22:54:25
It's sometimes useful to keep a mapping across program
invocations (e.g., because a space/time tradeoff makes it
worth keeping a cache of calculated metadata for some
objects).
This adds a persistent version of the map API which can be
backed by a flat memory store (like an mmap'd file). By
itself, it's not very pleasant to use, as the caller is
responsible for actually opening and mapping files. But it
provides the building blocks for disk caches, which will
come in the next patch.
Signed-off-by: Jeff King <redacted>
---
.gitignore | 1 +
Documentation/technical/api-map.txt | 77 +++++++++++++++++++
Makefile | 1 +
map-decl.h | 18 +++++
map-impl.h | 148 ++++++++++++++++++++++++++++++++++++
t/t0007-map.sh | 24 ++++++
test-map-persist.c | 125 ++++++++++++++++++++++++++++++
7 files changed, 394 insertions(+)
create mode 100644 test-map-persist.c
@@ -25,6 +25,21 @@ The decorate API provides a similar interface to map, but is restricted to using "struct object" as the key, and a void pointer as the value.+Persistent Maps+---------------++Maps come in two flavors: persistent and in-core. In-core maps are+represented by a hash table, and can contain any C type. Persistent maps+are backed by flat storage, such as an mmap'd file, and store values+between program runs. Key and value types must be serializable to+fixed-width byte values.++The flat storage is a sorted array of key/value pairs, with no+delimiters between pairs or between elements of a pair. Persistent maps+use an in-core map for newly-added values, and then merge the new+values into the flat storage on request.++ Defining New Map Types ----------------------
@@ -78,6 +93,39 @@ The following map defines are available: optimization to shrink the size of each map entry, at the cost of not being able to store `NULL` key pointers in the map.+`PERSIST`::++ Optional. If defined, functions for storing the map to disk are+ also created.++`KEY_SIZE`::++ Required by `PERSIST`. The fixed-width size of the on-disk+ representation of a key, in bytes.++`VALUE_SIZE`::++ Required by `PERSIST`. The fixed-width size of the on-disk+ representation of a value, in bytes.++`KEY_TO_DISK(KEY_ARG key, unsigned char *out)`::++ Required by `PERSIST`. A function that will convert the+ in-memory representation of a key into its on-disk+ representation. Note that the reverse transformation does not+ have to be possible.++`VALUE_TO_DISK(VALUE_ARG value, unsigned char *out)`::++ Required by `PERSIST`. A function that will convert the+ in-memory representation of a value into its on-disk+ representation.++`DISK_TO_VALUE(unsigned char *in, VALUE_TYPE *value)`::++ Required by `PERSIST`. A function that will convert the on-disk+ representation of a value into its in-memory representation.+ Data Structures ---------------
@@ -104,6 +152,14 @@ Each defined map type will have its own structure (e.g., `map_object_uint32`). need to use this type directly, unless you are enumerating all elements of a map.+`struct map_persist_NAME`::++ A persistent map. This struct should be initialized to+ all-zeroes. The `map` field contains a complete in-core map. The+ `disk_entries` and `disk_nr` fields specify the flat storage.+ These should not be set directly, but rather through the+ `attach` function.+ Functions ---------
@@ -127,6 +183,27 @@ Each defined map type will have its own set of access functions (e.g., defined, the key and value are passed in as `const KEY_TYPE *` and `const VALUE_TYPE *`, respectively.+`map_persist_get_NAME(struct map_persist_NAME *, KEY_TYPE key, VALUE_TYPE *value)`::++ Same as `map_get_NAME`, but for a persistent map.++`map_persist_set_NAME(struct map_persist_NAME *, KEY_TYPE key, VALUE_TYPE value)`::++ Same as `map_set_name`, but for a persistent map. It does+ not provide the "old" value for the key.++`map_persist_attach_NAME`::++ Attach storage from `buf` of size `len` bytes as the flat+ backing store for the map. The map does not copy the storage;+ the caller is responsible for making sure it stays around as+ long as the map does.++`map_persist_flush_NAME`::++ Merge in-core entries with those found in the backing store, and+ write the result to `fd`. Returns 0 for success, -1 for failure.+ Examples --------
@@ -92,3 +92,151 @@ int THIS(map_get)(struct THIS(map) *m,}return0;}++#ifdef PERSIST+staticconstunsignedchar*THIS(disk_lookup)(constunsignedchar*buf,intnr,+intksize,intvsize,+constunsignedchar*key)+{+unsignedlo=0,hi=nr;++do{+unsignedmi=(lo+hi)/2;+constunsignedchar*e=buf+mi*(ksize+vsize);+intcmp=memcmp(key,e,ksize);++if(!cmp)+returne+ksize;+if(cmp<0)+hi=mi;+else+lo=mi+1;+}while(lo<hi);++returnNULL;+}++intTHIS(map_persist_get)(structTHIS(map_persist)*m,+KEY_ARGkey,+VALUE_TYPE*value)+{+unsignedchardisk_key[KEY_SIZE];+constunsignedchar*disk_value;++if(THIS(map_get)(&m->mem,key,value))+return1;++if(!m->disk_entries)+return0;++KEY_TO_DISK(key,disk_key);+disk_value=THIS(disk_lookup)(m->disk_entries,m->disk_nr,+KEY_SIZE,VALUE_SIZE,disk_key);+if(disk_value){+DISK_TO_VALUE(disk_value,value);+return1;+}++return0;+}++intTHIS(map_persist_set)(structTHIS(map_persist)*m,+KEY_ARGkey,+VALUE_ARGvalue)+{+returnTHIS(map_set)(&m->mem,key,value,NULL);+}++voidTHIS(map_persist_attach)(structTHIS(map_persist)*m,+constunsignedchar*buf,+unsignedintlen)+{+m->disk_entries=buf;+m->disk_nr=len/(KEY_SIZE+VALUE_SIZE);+}++staticunsignedchar*THIS(flatten_mem)(structTHIS(map_persist)*m)+{+unsignedchar*ret,*out;+inti,nr;++out=ret=xmalloc(m->mem.nr*(KEY_SIZE+VALUE_SIZE));+nr=0;+for(i=0;i<m->mem.size;i++){+structTHIS(map_entry)*e=m->mem.hash+i;++if(!hash_used(e))+continue;++if(nr++==m->mem.nr)+die("BUG: map hash contained extra values");++KEY_TO_DISK(key_ref(e->key),out);+out+=KEY_SIZE;+VALUE_TO_DISK(value_ref(e->value),out);+out+=VALUE_SIZE;+}++if(nr!=m->mem.nr)+die("BUG: map hash had fewer values than claimed");++returnret;+}++staticintTHIS(keycmp)(constvoid*a,constvoid*b)+{+returnmemcmp(a,b,KEY_SIZE);+}++staticintTHIS(merge_entries)(intfd,+constunsignedchar*left,unsignednr_left,+constunsignedchar*right,unsignednr_right)+{+#define ADVANCE(name) \+do{\+name+=KEY_SIZE+VALUE_SIZE;\+nr_##name--;\+}while(0)+#define WRITE_ENTRY(name) \+do{\+if(write_in_full(fd,name,KEY_SIZE+VALUE_SIZE)<0)\+return-1;\+ADVANCE(name);\+}while(0)++while(nr_left&&nr_right){+intcmp=THIS(keycmp)(left,right);++/* skip duplicates, preferring left to right */+if(cmp==0)+ADVANCE(right);+elseif(cmp<0)+WRITE_ENTRY(left);+else+WRITE_ENTRY(right);+}+while(nr_left)+WRITE_ENTRY(left);+while(nr_right)+WRITE_ENTRY(right);++#undef WRITE_ENTRY+#undef ADVANCE++return0;+}++intTHIS(map_persist_flush)(structTHIS(map_persist)*m,intfd)+{+unsignedchar*mem_entries;+intr;++mem_entries=THIS(flatten_mem)(m);+qsort(mem_entries,m->mem.nr,KEY_SIZE+VALUE_SIZE,THIS(keycmp));++r=THIS(merge_entries)(fd,mem_entries,m->mem.nr,+m->disk_entries,m->disk_nr);+free(mem_entries);+returnr;+}+#endif
@@ -47,4 +47,28 @@ for type in pointer struct; do"done+test_expect_success'put some items in a persistent map''+test-map-persistfood:4a:1c:3b:2+'++test_expect_success'retrieve persistent items''+cat>expect<<-\EOF&&+c:3+a:1+e:notfound+EOF+test-map-persistfoocae>actual&&+test_cmpexpectactual+'++test_expect_success'new entries override disk entries''+cat>expect<<-\EOF&&+c:3+a:5+e:notfound+EOF+test-map-persistfooa:5cae>actual&&+test_cmpexpectactual+'+ test_done
@@ -0,0 +1,125 @@+#include"cache.h"++staticconstcharusage_msg[]=+"test-map-persist <file> [keys]";++staticinlineunsignedinthash_string(constchar*str,unsignedintn)+{+unsignedlonghash=0;++for(;*str;str++)+hash=(hash<<5)+*str;+returnhash%n;+}++staticinlineunsignedintstring_equal(constchar*a,constchar*b)+{+return!strcmp(a,b);+}++staticinlinevoidstring_to_disk(constchar*s,unsignedchar*out)+{+/*+*weneedafixed-widthrepresentation,solet'sjuststore10bytes,+*paddedwithzeroes+*/+intlen=strlen(s);+if(len>10)+len=10;+memcpy(out,s,len);+memset(out+len,0,10-len);+}++staticinlinevoiduint32_to_disk(uint32_tv,unsignedchar*out)+{+v=htonl(v);+memcpy(out,&v,4);+}++staticinlinevoiddisk_to_uint32(constunsignedchar*in,uint32_t*v)+{+memcpy(v,in,4);+*v=ntohl(*v);+}++#define NAME string_uint32+#define PERSIST+#define KEY_TYPE const char *+#define KEY_SIZE 10+#define KEY_TO_DISK string_to_disk+#define KEY_EQUAL string_equal+#define HASH hash_string+#define DISK_LOOKUP_FUN lookup_string+#define SENTINEL_NULL+#define VALUE_TYPE uint32_t+#define VALUE_SIZE 4+#define VALUE_TO_DISK uint32_to_disk+#define DISK_TO_VALUE disk_to_uint32+#include"map-decl.h"+#include"map-impl.h"+#include"map-done.h"++staticvoidopen_map(constchar*path,structmap_persist_string_uint32*m)+{+intfd;+structstatsb;+constunsignedchar*buf;++fd=open(path,O_RDONLY);+if(fd<0)+return;++fstat(fd,&sb);+buf=xmmap(NULL,sb.st_size,PROT_READ,MAP_PRIVATE,fd,0);+close(fd);++map_persist_attach_string_uint32(m,buf,sb.st_size);+}++staticvoidflush_map(constchar*path,structmap_persist_string_uint32*m)+{+chartmp[1024];+intfd;++snprintf(tmp,sizeof(tmp),"%s.tmp",path);+fd=open(tmp,O_WRONLY|O_CREAT,0666);+if(fd<0)+die_errno("unable to open '%s' for writing",tmp);+if(map_persist_flush_string_uint32(m,fd)<0||close(fd)<0)+die_errno("unable to write new map");+if(rename(tmp,path)<0)+die_errno("unable to rename new map into place");+}++intmain(intargc,constchar**argv)+{+structmap_persist_string_uint32m={0};+constchar*path;+constchar*spec;++argv++;+path=*argv++;+if(!path)+usage(usage_msg);++open_map(path,&m);++while((spec=*argv++)){+char*colon=strchr(spec,':');+if(colon){+*colon++='\0';+map_persist_set_string_uint32(&m,spec,atoi(colon));+}+else{+uint32_tvalue;+if(map_persist_get_string_uint32(&m,spec,&value))+printf("%s: %d\n",spec,value);+else+printf("%s: not found\n",spec);+}+}++flush_map(path,&m);++return0;+}
From: Jeff King <hidden> Date: 2016-06-15 22:54:25
There are some calculations that git makes repeatedly, even
though the results are invariant for a certain input (e.g.,
the patch-id of a certain commit). We can make a space/time
tradeoff by caching these on disk between runs.
Even though these may be immutable for a certain commit, we
don't want to directly store the results in the commit
objects themselves, for a few reasons:
1. They are not necessarily used by all algorithms, so
bloating the commit object might slow down other
algorithms.
2. Because they can be calculated from the existing
commits, they are redundant with the existing
information. Thus they are an implementation detail of
our current algorithms, and should not be cast in stone
by including them in the commit sha1.
3. They may only be immutable under a certain set of
conditions (e.g., which grafts or replace refs we are
using). Keeping the storage external means we can
invalidate and regenerate the cache whenever those
conditions change.
The persistent map API already provides the storage we need.
This new API takes care of the details of opening and
closing the cache files automatically. Callers need only get
and set values as they see fit.
Signed-off-by: Jeff King <redacted>
---
Documentation/technical/api-metadata-cache.txt | 67 ++++++++++
Makefile | 2 +
metadata-cache.c | 169 +++++++++++++++++++++++++
metadata-cache.h | 8 ++
4 files changed, 246 insertions(+)
create mode 100644 Documentation/technical/api-metadata-cache.txt
create mode 100644 metadata-cache.c
create mode 100644 metadata-cache.h
@@ -0,0 +1,67 @@+metadata cache API+==================++The metadata cache API provides simple-to-use, persistent key/value+storage. It is built on the link:api-map.html[map API], so keys and+values can have any serializable type.++Caches are statically allocated, and no explicit initialization is+required. Callers can simply call the "get" and "set" functions for a+given cache. At program exit, any new entries in the cache are flushed+to disk.+++Defining a New Cache+--------------------++You need to provide three pieces of information to define a new cache:++name::+ This name will be used both as part of the C identifier and as+ part of the filename under which the cache is stored. Restrict+ the characters used to alphanumerics and underscore.++map::+ The type of map (declared by `DECLARE_MAP`) that this cache will+ store.++validity::+ A function that will generate a 20-byte "validity token"+ representing the conditions under which the cache is valid.+ For example, a cache that depended on the structure of the+ history graph would be valid only under a given set of grafts+ and replace refs. That set could be stirred into a sha1 and used+ as a validity token.++You must declare the cache in metadata-cache.h using+`DECLARE_METADATA_CACHE`, and then implement it in metadata-cache.c+using `IMPLEMENT_METADATA_CACHE`.+++Using a Cache+-------------++Interaction with a cache consists entirely of getting and setting+values. No initialization or cleanup is required. The get and set+functions mirror their "map" counterparts; see the+link:api-map.html[map API] for details.+++File Format+-----------++Cache files are stored in the $GIT_DIR/cache directory. Each cache gets+its own directory, named after the `name` parameter in the cache+definition. Within each directory is a set of files, one cache per file,+named after their validity tokens. Caches for multiple sets of+conditions can simultaneously exist, and git will use whichever is+appropriate.++The files themselves consist of an 8-byte header. The first four bytes+are the magic sequence "MTAC" (for "MeTA Cache"), followed by a 4-byte+version number, in network byte order. This document describes version+1.++The rest of the file consists of the persistent map data. This is a+compact, sorted list of keys and values; see the link:api-map.html[map+API] for details.
From: Jeff King <hidden> Date: 2016-06-15 22:54:25
This speeds up estimate_similarity by caching the similarity
score of pairs of blob sha1s.
Signed-off-by: Jeff King <redacted>
---
Some interesting things to time with this are:
- "git log --raw -M" on a repo with a lot of paths or a lot of renames
(I found on git.git, the speedup was not that impressive)
- "git log --raw -C -C" on any repo (this speeds up a lot in git.git).
- "git show -M" on commits with very large blobs
cache.h | 1 +
diff.c | 6 ++++++
diffcore-rename.c | 11 ++++++++++-
3 files changed, 17 insertions(+), 1 deletion(-)
@@ -6,6 +6,7 @@#include"diffcore.h"#include"hash.h"#include"progress.h"+#include"metadata-cache.h"/* Table of rename/copy destinations */
@@ -137,7 +138,8 @@ static int estimate_similarity(struct diff_filespec *src,*/unsignedlongmax_size,delta_size,base_size,src_copied,literal_added;unsignedlongdelta_limit;-intscore;+uint32_tscore;+structsha1pairpair;/* We deal only with regular files. Symlink renames are handled*onlywhentheyareexactmatches---inotherwords,noedits
@@ -175,6 +177,11 @@ static int estimate_similarity(struct diff_filespec *src,if(max_size*(MAX_SCORE-minimum_score)<delta_size*MAX_SCORE)return0;+hashcpy(pair.one,src->sha1);+hashcpy(pair.two,dst->sha1);+if(diff_cache_renames&&rename_cache_get(&pair,&score))+returnscore;+if(!src->cnt_data&&diff_populate_filespec(src,0))return0;if(!dst->cnt_data&&diff_populate_filespec(dst,0))
@@ -195,6 +202,8 @@ static int estimate_similarity(struct diff_filespec *src,score=0;/* should not happen */elsescore=(int)(src_copied*MAX_SCORE/max_size);+if(diff_cache_renames)+rename_cache_set(&pair,score);returnscore;}
From: Junio C Hamano <hidden> Date: 2016-06-15 22:54:25
Jeff King [off-list ref] writes:
There are some calculations that git makes repeatedly, even
though the results are invariant for a certain input (e.g.,
the patch-id of a certain commit). We can make a space/time
tradeoff by caching these on disk between runs.
Even though these may be immutable for a certain commit, we
don't want to directly store the results in the commit
objects themselves, for a few reasons:
1. They are not necessarily used by all algorithms, so
bloating the commit object might slow down other
algorithms.
2. Because they can be calculated from the existing
commits, they are redundant with the existing
information. Thus they are an implementation detail of
our current algorithms, and should not be cast in stone
by including them in the commit sha1.
3. They may only be immutable under a certain set of
conditions (e.g., which grafts or replace refs we are
using). Keeping the storage external means we can
invalidate and regenerate the cache whenever those
conditions change.
4. The algorithm used to compute such values could improve over
time. The same advantage argument as 3 applies to this case.
From: Junio C Hamano <hidden> Date: 2016-06-15 22:54:25
Jeff King [off-list ref] writes:
It is frequently useful to have a fast, generic data
structure mapping keys to values. We already have something
like this in the "decorate" API, but it has two downsides:
1. The key type must always be a "struct object *".
2. The value type is a void pointer, which means it is
inefficient and cumbersome for storing small values.
One must either encode their value inside the void
pointer, or allocate additional storage for the pointer
to point to.
This patch introduces a generic map data structure, mapping
keys of arbitrary type to values of arbitrary type.
Does the type of keys in a map have to be of the same size, or can a
key of a type with variable size (e.g. struct with a flex member at
the end)? Same question for the type of values.
Is the type of keys in a map required to have a total order over it,
or is it suffice only to have equality defined?
The latter might matter once we start talking about a huge map that
we may not want to hold in-core.
From: Jeff King <hidden> Date: 2016-06-15 22:54:26
On Sat, Aug 04, 2012 at 03:49:12PM -0700, Junio C Hamano wrote:
Jeff King [off-list ref] writes:
quoted
There are some calculations that git makes repeatedly, even
though the results are invariant for a certain input (e.g.,
the patch-id of a certain commit). We can make a space/time
tradeoff by caching these on disk between runs.
Even though these may be immutable for a certain commit, we
don't want to directly store the results in the commit
objects themselves, for a few reasons:
1. They are not necessarily used by all algorithms, so
bloating the commit object might slow down other
algorithms.
2. Because they can be calculated from the existing
commits, they are redundant with the existing
information. Thus they are an implementation detail of
our current algorithms, and should not be cast in stone
by including them in the commit sha1.
3. They may only be immutable under a certain set of
conditions (e.g., which grafts or replace refs we are
using). Keeping the storage external means we can
invalidate and regenerate the cache whenever those
conditions change.
4. The algorithm used to compute such values could improve over
time. The same advantage argument as 3 applies to this case.
Yeah, agreed. That commit message is a year old, and was written for an
earlier iteration of the patch which was used for caching commit
generations. There's not really a better algorithm there, but your
comment certainly applies to rename similarities.
-Peff
From: Jeff King <hidden> Date: 2016-06-15 22:54:26
On Sat, Aug 04, 2012 at 03:58:10PM -0700, Junio C Hamano wrote:
Jeff King [off-list ref] writes:
quoted
It is frequently useful to have a fast, generic data
structure mapping keys to values. We already have something
like this in the "decorate" API, but it has two downsides:
1. The key type must always be a "struct object *".
2. The value type is a void pointer, which means it is
inefficient and cumbersome for storing small values.
One must either encode their value inside the void
pointer, or allocate additional storage for the pointer
to point to.
This patch introduces a generic map data structure, mapping
keys of arbitrary type to values of arbitrary type.
Does the type of keys in a map have to be of the same size, or can a
key of a type with variable size (e.g. struct with a flex member at
the end)? Same question for the type of values.
Both have to be fixed size, since we represent the hash table using an
array. But there is nothing stopping you from storing a fixed-size
pointer to a variable-sized item (that is what is happening with "struct
object *", anyway; the actual storage is inside a "struct commit",
"struct tree", etc). But then you get the accompanying memory-management
issues (which are easy for "struct object", as our policy is to keep a
global valid-until-the-program-exits store of all objects we ever see).
Is the type of keys in a map required to have a total order over it,
or is it suffice only to have equality defined?
No, you only have to define equality. However, for the later patch which
adds a persistent backing store, you need to be able to serialize keys
to a byte representation, which provides an implicit total order (by
sorting the bytes).
The latter might matter once we start talking about a huge map that
we may not want to hold in-core.
A minor fixup, but this should obviously be "map_persist_##maptype". It
doesn't matter for this series (since we only instantiate one cache, and
it uses a sha1pair_uint32 map), but obviously this was meant to be
generic...
-Peff