* Re: [PATCH 07/11] object: try naive cuckoo hashing
From: George Spelvin @ 2011-08-13 19:12 UTC (permalink / raw)
To: gitster, linux; +Cc: git
In-Reply-To: <20110813102244.9033.qmail@science.horizon.com>
I've been doing a lot of reading on Cuckoo hashing.
Yes, the single-table variant is described and used. However, the
insertion procedure is not the way you do it.
Also, d-ary Cuckoo hashing (also called d-Cuckoo hashing) where you use
more than 2 hash functions is also used.
The insertion algorithm, however, is not really agreed on.
One algorithm (mostly proposed for hardware) uses d separate tables.
Every entry displaced from table i is displaced to table i+1 (mod d).
http://infoscience.epfl.ch/record/164147/files/cuckoo_dir_hpca2011_camera_ready.pdf
In the single-table case, and in general, however, a displaced entry
has more than one possible new location. This leads to the question of how
to choose.
One proposal is to do a breadth-first search looking for a path to
a free slot. It's provable that this will succeed with high probability
before the exponential growth of the breadth of the search tree
gets too bad.
See "Space Efficient Hash Tables with Worst Case Constant Access Time"
http://www.itu.dk/people/pagh/papers/d-cuckoo-jour.pdf
Another suggested tehcnique is to just pick an alternative at random
and proceed. This is recommended in e.g.
"Efficient Hash Probes on Modern Processors"
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.1189&rep=rep1&type=pdf
Both of these lead to rather complex implementations. The random number
generator is probably simpler than the breadth-first search, but either way
there's a bunch of auxiliary code.
Sticking with two hash functions, but using multi-entry buckets is
definitely an attractive possibility.
^ permalink raw reply
* Re: What's cooking in git.git (Aug 2011, #03; Thu, 11) : Guidance for new contributors?
From: Philip Oakley @ 2011-08-13 18:40 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7vr54rpogf.fsf@alter.siamese.dyndns.org>
From: "Junio C Hamano" <gitster@pobox.com>
Subject: What's cooking in git.git (Aug 2011, #03; Thu, 11)
> Here are the topics that have been cooking. Commits prefixed with '-' are
> only in 'pu' while commits prefixed with '+' are in 'next'.
>
> I am envisioning that we would declare feature freeze after most of the
> topics that are in 'next' as of today graduate to 'master' for the next
> release, and keep the remainder cooking for the cycle after that.
> Hopefully
> that would happen around 24th.
>
Would it it be possible to include a regular link to an explanation for new
contributors? It would guide and encourage any new readers of the list.
Would this one be suitable?
+ Guidance for contributions at
https://git.wiki.kernel.org/index.php/GitCommunity#Submitting
> --------------------------------------------------
> [New Topics]
> ....
Philip Oakley
Scotland UK.
^ permalink raw reply
* Re: Reusing changes after renaming a file (Re: [PATCH 5/6] sequencer: Expose API to cherry-picking machinery)
From: Jonathan Nieder @ 2011-08-13 18:32 UTC (permalink / raw)
To: Ramkumar Ramachandra
Cc: Daniel Barkalow, Git List, Junio C Hamano, Christian Couder,
Jeff King
In-Reply-To: <CALkWK0mDdYTahhDx9_7-4AP8iuvkWMu1wHhQnmUcatEXiDiuTA@mail.gmail.com>
Ramkumar Ramachandra wrote:
> $ git cherry-pick -Xrename-threshold=90 sequencer~1
> [test 7400609] sequencer: Expose API to cherry-picking machinery
> 3 files changed, 256 insertions(+), 1247 deletions(-)
> rewrite builtin/revert.c (81%)
> rename builtin/revert.c => sequencer.c (81%)
>
> Is it supposed to influence the diffstat? I don't see any conflict
> markers in sequencer.c. I can see lots of unintelligent (and useless)
> conflict markers in builtin/revert.c.
Perhaps "git merge-recursive" and its callers don't use the equivalent
of -B, so it doesn't look like a rename to them. Cases involving
plain renames work fine for me.
^ permalink raw reply
* Re: Reusing changes after renaming a file (Re: [PATCH 5/6] sequencer: Expose API to cherry-picking machinery)
From: Ramkumar Ramachandra @ 2011-08-13 18:20 UTC (permalink / raw)
To: Jonathan Nieder
Cc: Daniel Barkalow, Git List, Junio C Hamano, Christian Couder,
Jeff King
In-Reply-To: <20110813175012.GD1494@elie.gateway.2wire.net>
Hi Jonathan,
Disclaimer: I'm sorry if I sound incredibly stupid. I know nothing
about how the diffing algorithm works.
Jonathan Nieder writes:
> Ramkumar Ramachandra wrote:
>> Hm, I was actually thinking of a much less ambitious helper that would
>> kick in when the heuristic correlation between two files is above a
>> certain threshold.
>
> Doesn't that already work? For example:
>
> git cherry-pick -Xrename-threshold=50 foo
Okay, I'm still trying to figure out what this does. It's supposed to
"influence the rename detection" according to the 1.7.4 release notes.
I tried:
$ git cherry-pick -Xrename-threshold=90 sequencer~1
[test 7400609] sequencer: Expose API to cherry-picking machinery
3 files changed, 256 insertions(+), 1247 deletions(-)
rewrite builtin/revert.c (81%)
rename builtin/revert.c => sequencer.c (81%)
Is it supposed to influence the diffstat? I don't see any conflict
markers in sequencer.c. I can see lots of unintelligent (and useless)
conflict markers in builtin/revert.c. What am I supposed to be
looking at?
-- Ram
^ permalink raw reply
* Reusing changes after renaming a file (Re: [PATCH 5/6] sequencer: Expose API to cherry-picking machinery)
From: Jonathan Nieder @ 2011-08-13 17:50 UTC (permalink / raw)
To: Ramkumar Ramachandra
Cc: Daniel Barkalow, Git List, Junio C Hamano, Christian Couder,
Jeff King
In-Reply-To: <CALkWK0=seEY+O8qmNKoPyYPW-QT9zpwGsh8SB89qcd6kUQRdKg@mail.gmail.com>
Ramkumar Ramachandra wrote:
> Hm, I was actually thinking of a much less ambitious helper that would
> kick in when the heuristic correlation between two files is above a
> certain threshold.
Doesn't that already work? For example:
git cherry-pick -Xrename-threshold=50 foo
^ permalink raw reply
* Re: [PATCH 5/6] sequencer: Expose API to cherry-picking machinery
From: Ramkumar Ramachandra @ 2011-08-13 17:40 UTC (permalink / raw)
To: Daniel Barkalow
Cc: Jonathan Nieder, Git List, Junio C Hamano, Christian Couder,
Jeff King
In-Reply-To: <alpine.LNX.2.00.1108131215170.2056@iabervon.org>
Hi Daniel,
Daniel Barkalow writes:
>> 1. Make prepare_revs and walk_revs_populate_todo return errors to be
>> handled by callers. This is a fairly small patch that can come before
>> the big "code moving patch".
>
> This makes sense. If you type "git log --stat=foo", you don't get a
> diff usage message, even though it's an error parsing options that were
> originally part of diff.
Yes :) I really liked the "revert: Propagate errors upwards from
do_pick_commit" patch. I hope we improve the error handling in other
parts of Git soon.
>> 2. Duplicate action_name in both files. I don't think it's too
>> serious, and we can fix this later.
>
> This is actually probably even a good idea, because the two functions
> might actually want to give different results. Maybe revert.c will end up
> doing different sequencer operations depending on whether the commit is a
> merge, but if revert.c has to give an error, it would call it the same
> thing either way, because the difference doesn't matter at the level of
> detail the revert.c works at; on the other hand, sequencer.c would want to
> distinguish the cases so that it is explaining exactly what it's trying to
> do in this step because it matters to how the issue would be resolved.
>
> Of course, at the point where you move the code, you only have one piece
> of code that you're starting from, so they'll be the same. But you might
> want to name them differently.
Excellent suggestion- I want to create a differentiation between the
sequencer "pick" action and the builtin "cherry-pick" operation. I
mentioned earlier that I wanted the sequencer to be more than a fast
git-shell. It'll be interesting to see the kinds of composite
"actions" we invent later; especially ones that only make sense in the
context of sequencing commits.
>> It has been enormously annoying to work with this "code moving patch":
>> everytime I make some changes to the earlier patches, I have to
>> recreate this one by hand; rebase offers no help whatsoever. After
>> throwing away code based on this patch several times, I learnt my
>> lesson and restricted my series to avoid building on this patch. I
>> consider this a very serious glitch and I'm interested in fixing it.
>> Thoughts?
>
> It's a hard problem, although likely worthwhile to solve. But only when
> you're not doing anything else, because it's complicated and will take you
> far afield. Essentially, what you need to do is implement a diff algorithm
> that can detect reorganization (or copying) of sections; this isn't
> something you can represent in unified diff output, but that's okay
> because you're not going to output it. You merge two of these results and
> apply the result to the base, which gives you a file (potentially with
> conflicts, which is another interesting issue because you have to
> represent and explain them somehow).
Hm, I was actually thinking of a much less ambitious helper that would
kick in when the heuristic correlation between two files is above a
certain threshold. Your idea is better! It would be totally awesome
if we could modify the diffing algorithm to work between files,
although I can't even imagine where to start. Oh, and I think we have
to go far beyond the traditional in-file conflict markers to resolve
conflicts. Pretty insane challenge :D I'm definitely not experienced
enough to take this on now, although I hope to be good enough someday.
> *: bisect could be using sequencer in order to handle the situation where
> the user has said "commit A is good, commit B is bad, commit C breaks my
> system in a way that's unrelated"; the system should then be able to check
> out a maybe-bad commit and revert C from it, but it would be doing this in
> response to an instruction from the user: "give me something to test
> next", and would have to present errors differently.
Thanks for the interesting sidenote.
-- Ram
^ permalink raw reply
* Re: [PATCH 2/2] On Cygwin support both UNIX and DOS style path-names
From: Pascal Obry @ 2011-08-13 17:34 UTC (permalink / raw)
To: Ramsay Jones; +Cc: git
In-Reply-To: <4E443D1B.60306@ramsay1.demon.co.uk>
Le 11/08/2011 22:35, Ramsay Jones a écrit :
> ... could you please correct your commit message. Thanks!
Done, thanks for your review.
Pascal.
--
--|------------------------------------------------------
--| Pascal Obry Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--| http://www.obry.net - http://v2p.fr.eu.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver keys.gnupg.net --recv-key F949BD3B
^ permalink raw reply
* [PATCH 0/2] Support backslash under Cygwin
From: Pascal Obry @ 2011-08-13 17:33 UTC (permalink / raw)
To: git
This is a third version of this patch. In this version only the
log for PATCH 2/2 has been corrected.
^ permalink raw reply
* Re: [PATCH 5/6] sequencer: Expose API to cherry-picking machinery
From: Jonathan Nieder @ 2011-08-13 17:06 UTC (permalink / raw)
To: Ramkumar Ramachandra
Cc: Git List, Junio C Hamano, Christian Couder, Daniel Barkalow,
Jeff King
In-Reply-To: <CALkWK0migSRUmhPp0069O_NiRs3gQJbrU8QLdwUJ-kUYAsLz4Q@mail.gmail.com>
Ramkumar Ramachandra wrote:
> Jonathan Nieder writes:
>> Another thought. I wonder if it's possible to leave
>> sequencer_parse_args() private to builtin/revert.c, making the split
>> a little more logical:
>
> Yes, I'd like this too. However, there are two new issues:
> revert_or_cherry_pick_usage and action_name. The former has two
> callsites: one in prepare_revs (in sequencer.c) and another in
> parse_args (in builtin/revert.c).
So it sounds like the answer is "no, it's not possible without
further changes". Alas. :) Thanks for checking.
(Q. Wait, what further changes?
A. The above suggests that the setup_revisions call should also be
the responsibility of the builtin, and that it could communicate
revs and other rev-list options using a
struct rev_info *revs;
instead of
int commit_argc;
const char **commit_argv;
Like this, maybe:
builtin/revert.c | 52 ++++++++++++++++++++++++++++++----------------------
1 files changed, 30 insertions(+), 22 deletions(-)
diff --git i/builtin/revert.c w/builtin/revert.c
index 8b452e81..f602ece0 100644
--- i/builtin/revert.c
+++ w/builtin/revert.c
@@ -55,13 +55,14 @@ struct replay_opts {
int allow_rerere_auto;
int mainline;
- int commit_argc;
- const char **commit_argv;
/* Merge strategy */
const char *strategy;
const char **xopts;
size_t xopts_nr, xopts_alloc;
+
+ /* Only used by the default subcommand ("git revert <revs>") */
+ struct rev_info *revs;
};
#define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"
@@ -164,7 +165,7 @@ static void parse_args(int argc, const char **argv, struct replay_opts *opts)
die(_("program error"));
}
- opts->commit_argc = parse_options(argc, argv, NULL, options, usage_str,
+ argc = parse_options(argc, argv, NULL, options, usage_str,
PARSE_OPT_KEEP_ARGV0 |
PARSE_OPT_KEEP_UNKNOWN);
@@ -201,9 +202,6 @@ static void parse_args(int argc, const char **argv, struct replay_opts *opts)
NULL);
}
- else if (opts->commit_argc < 2)
- usage_with_options(usage_str, options);
-
if (opts->allow_ff)
verify_opt_compatible(me, "--ff",
"--signoff", opts->signoff,
@@ -211,7 +209,23 @@ static void parse_args(int argc, const char **argv, struct replay_opts *opts)
"-x", opts->record_origin,
"--edit", opts->edit,
NULL);
- opts->commit_argv = argv;
+
+ if (opts->subcommand != REPLAY_NONE) {
+ opts->revs = NULL;
+ if (argc > 1)
+ usage_with_options(usage_str, options);
+ } else {
+ opts->revs = xmalloc(sizeof(*opts->revs));
+ init_revisions(opts->revs, NULL);
+ opts->revs->no_walk = 1;
+
+ if (argc < 2)
+ usage_with_options(usage_str, options);
+
+ argc = setup_revisions(argc, argv, opts->revs, NULL);
+ if (argc > 1)
+ usage_with_options(usage_str, options);
+ }
}
struct commit_message {
@@ -612,23 +626,15 @@ static int do_pick_commit(struct commit *commit, struct replay_opts *opts)
return res;
}
-static void prepare_revs(struct rev_info *revs, struct replay_opts *opts)
+static void prepare_revs(struct replay_opts *opts)
{
- int argc;
-
- init_revisions(revs, NULL);
- revs->no_walk = 1;
if (opts->action != REVERT)
- revs->reverse = 1;
+ opts->revs->reverse ^= 1;
- argc = setup_revisions(opts->commit_argc, opts->commit_argv, revs, NULL);
- if (argc > 1)
- usage(*revert_or_cherry_pick_usage(opts));
-
- if (prepare_revision_walk(revs))
+ if (prepare_revision_walk(opts->revs))
die(_("revision walk setup failed"));
- if (!revs->commits)
+ if (!opts->revs->commits)
die(_("empty commit set passed"));
}
@@ -825,14 +831,13 @@ static void read_populate_opts(struct replay_opts **opts_ptr)
static void walk_revs_populate_todo(struct commit_list **todo_list,
struct replay_opts *opts)
{
- struct rev_info revs;
struct commit *commit;
struct commit_list **next;
- prepare_revs(&revs, opts);
+ prepare_revs(opts);
next = todo_list;
- while ((commit = get_revision(&revs)))
+ while ((commit = get_revision(opts->revs)))
next = commit_list_append(commit, next);
}
@@ -955,6 +960,9 @@ static int pick_revisions(struct replay_opts *opts)
struct commit_list *todo_list = NULL;
unsigned char sha1[20];
+ if (opts->subcommand == REPLAY_NONE)
+ assert(opts->revs);
+
read_and_refresh_cache(opts);
/*
--
)
^ permalink raw reply related
* Re: [PATCH 5/6] sequencer: Expose API to cherry-picking machinery
From: Daniel Barkalow @ 2011-08-13 16:45 UTC (permalink / raw)
To: Ramkumar Ramachandra
Cc: Jonathan Nieder, Git List, Junio C Hamano, Christian Couder,
Jeff King
In-Reply-To: <CALkWK0migSRUmhPp0069O_NiRs3gQJbrU8QLdwUJ-kUYAsLz4Q@mail.gmail.com>
[-- Attachment #1: Type: TEXT/PLAIN, Size: 3676 bytes --]
On Sat, 13 Aug 2011, Ramkumar Ramachandra wrote:
> Hi again,
>
> Jonathan Nieder writes:
> > Another thought. I wonder if it's possible to leave
> > sequencer_parse_args() private to builtin/revert.c, making the split
> > a little more logical:
>
> Yes, I'd like this too. However, there are two new issues:
> revert_or_cherry_pick_usage and action_name. The former has two
> callsites: one in prepare_revs (in sequencer.c) and another in
> parse_args (in builtin/revert.c). Unfortunately, action_name is even
> more complicated to get rid of: the information from it is used all
> over the place.
One thing to consider is that sequencer.c will be used by all sorts of
different builtins, which are each implementing instructions given
differently by the user. Just because a message makes sense as output from
revert.c doesn't mean it will make sense from (for example) bisect*.
> Attempting to attack the problems one by one:
> 1. Make prepare_revs and walk_revs_populate_todo return errors to be
> handled by callers. This is a fairly small patch that can come before
> the big "code moving patch".
This makes sense. If you type "git log --stat=foo", you don't get a
diff usage message, even though it's an error parsing options that were
originally part of diff.
> 2. Duplicate action_name in both files. I don't think it's too
> serious, and we can fix this later.
This is actually probably even a good idea, because the two functions
might actually want to give different results. Maybe revert.c will end up
doing different sequencer operations depending on whether the commit is a
merge, but if revert.c has to give an error, it would call it the same
thing either way, because the difference doesn't matter at the level of
detail the revert.c works at; on the other hand, sequencer.c would want to
distinguish the cases so that it is explaining exactly what it's trying to
do in this step because it matters to how the issue would be resolved.
Of course, at the point where you move the code, you only have one piece
of code that you're starting from, so they'll be the same. But you might
want to name them differently.
> It has been enormously annoying to work with this "code moving patch":
> everytime I make some changes to the earlier patches, I have to
> recreate this one by hand; rebase offers no help whatsoever. After
> throwing away code based on this patch several times, I learnt my
> lesson and restricted my series to avoid building on this patch. I
> consider this a very serious glitch and I'm interested in fixing it.
> Thoughts?
It's a hard problem, although likely worthwhile to solve. But only when
you're not doing anything else, because it's complicated and will take you
far afield. Essentially, what you need to do is implement a diff algorithm
that can detect reorganization (or copying) of sections; this isn't
something you can represent in unified diff output, but that's okay
because you're not going to output it. You merge two of these results and
apply the result to the base, which gives you a file (potentially with
conflicts, which is another interesting issue because you have to
represent and explain them somehow).
*: bisect could be using sequencer in order to handle the situation where
the user has said "commit A is good, commit B is bad, commit C breaks my
system in a way that's unrelated"; the system should then be able to check
out a maybe-bad commit and revert C from it, but it would be doing this in
response to an instruction from the user: "give me something to test
next", and would have to present errors differently.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Re: [PATCH 2/2] On Cygwin support both UNIX and DOS style path-names
From: Ramsay Jones @ 2011-08-11 20:35 UTC (permalink / raw)
To: pascal; +Cc: git
In-Reply-To: <4E419AB3.7090405@obry.net>
Pascal Obry wrote:
> Le 09/08/2011 19:24, Ramsay Jones a écrit :
>> Pascal Obry wrote:
>>> In fact Cygwin supports both, so make Git agree with this.
>>> The failing case is when a file is committed in a sub-dir of the
>>> repository using a log message from a file specified with a DOS
>>> style path-name. To reproduce:
>>>
>>> $ cd src
>>> $ git commit -F c:\tmp\log.txt file.c
>>> fatal: could not read log file 'src/c:\tmp\log.txt': No such file \
>>> or directory.
>> Hmm, are you using bash or cmd.exe? Using bash I get the following:
>
> bash.
Ah, OK. The example in your commit message looked odd (ie incorrect) which
made me think that you were probably using cnd.exe, so ...
>> $ cd src
>> $ git commut -F c:\tmp\log.txt file.c
>> fatal: could not read file 'src/c:tmplog.txt': No such file or directory
>> $
>>
>> Which is what I would expect of (any) posix shell, viz:
>>
>> $ ls c:\
>> > ^C
>> $ ls c:\\
>> AUTOEXEC.BAT* NTDETECT.COM* WATCOM/ msysgit/
>> CMPNENTS/ Program Files/ WINDOWS/ msysgit-old/
>> CONFIG.SYS* RECYCLER/ boot.ini* ntldr*
>> Documents and Settings/ SUPPORT/ cygwin/ pagefile.sys
>> I386/ SWSTAMP.TXT* cygwintemp/ ssl/
>> IO.SYS* System Volume Information/ dm/ uname/
>> MSDOS.SYS* TOOLSCD/ dm840/ zlib/
>> MSOCache/ VALUEADD/ hiberfil.sys
>
> Exactly, \\ this is what I have used and this is the bug. Cygwin
> supports ls c:\\ so should Cygwin/Git. My quoted example was missing the
> escape \.
... could you please correct your commit message. Thanks!
ATB,
Ramsay Jones
^ permalink raw reply
* Re: [PATCH 4/6] revert: Allow mixed pick and revert instructions
From: Ramkumar Ramachandra @ 2011-08-13 16:07 UTC (permalink / raw)
To: Jonathan Nieder
Cc: Git List, Junio C Hamano, Christian Couder, Daniel Barkalow,
Jeff King
In-Reply-To: <20110811201245.GH2277@elie.gateway.2wire.net>
Hi,
Jonathan Nieder writes:
> Ramkumar Ramachandra wrote:
>> Change the way the instruction parser works, allowing arbitrary
>> (action, operand) pairs to be parsed.
>
> Parse the instruction list in .git/sequencer/todo as a list
> of (action, operand) pairs, instead of assuming all instructions
> use the same action.
Fixed. Thanks :)
>> @@ -517,7 +517,8 @@ static int do_pick_commit(struct commit *commit, struct replay_opts *opts)
>> /* TRANSLATORS: The first %s will be "revert" or
>> "cherry-pick", the second %s a SHA1 */
>> return error(_("%s: cannot parse parent commit %s"),
>> - action_name(opts), sha1_to_hex(parent->object.sha1));
>> + action == REPLAY_REVERT ? "revert" : "cherry-pick",
>> + sha1_to_hex(parent->object.sha1));
>
> My first thought was "why stop using the helper function action_name"?
> But now I see that it previously came from "opts" (i.e., the command
> line) and now comes from the todo file.
>
> The command name there was never really important except when
> cherry-pick or revert is being called by a script, and the message
> indicates which command was having trouble parsing the commit. If I
> am using "git cherry-pick --continue" to continue after a failed
> revert, I suspect action_name(opts) ["cherry-pick: "] would actually be
> more sensible than the command name corresponding to the particular
> pick/revert line.
You're right. Removed this hunk.
> Maybe something like
>
> len = strchrnul(p, '\n') - p;
> if (len > 255)
> len = 255;
> return error(_("Unrecognized action: %.*s"), (int) len, p);
>
> would do.
Excellent idea! I fixed the buffer overflow message to do this too.
By the way, shouldn't error() do this?
> Could we can make this error message more clearly suggest that it's
> giving context to the error above it? For example, something vaguely
> like
>
> error: unrecognized action: reset c78a78c9 Going back
> error: on line 7
Good suggestion. Fixed.
> Does a "cherry-pick --continue" in this scenario skip the first commit
> in the todo list? Should it?
It shouldn't and it doesn't. See how read_populate_opts and
read_populate_todo are called before the segment that drops the first
commit.
-- Ram
^ permalink raw reply
* Re: [PATCH 5/6] sequencer: Expose API to cherry-picking machinery
From: Ramkumar Ramachandra @ 2011-08-13 14:00 UTC (permalink / raw)
To: Jonathan Nieder
Cc: Git List, Junio C Hamano, Christian Couder, Daniel Barkalow,
Jeff King
In-Reply-To: <20110811215650.GA13839@elie.gateway.2wire.net>
Hi again,
Jonathan Nieder writes:
> Ramkumar Ramachandra wrote:
>> --- a/sequencer.h
>> +++ b/sequencer.h
>> @@ -7,7 +7,32 @@
>> #define SEQ_TODO_FILE "sequencer/todo"
>> #define SEQ_OPTS_FILE "sequencer/opts"
>>
>> +#define COMMIT_MESSAGE_INIT { NULL, NULL, NULL, NULL, NULL };
>
> I don't think this should be exposed. The rest seems pretty sane,
> though I haven't read the patch carefully.
Gah, my stupidity. What sense does it make to expose
COMMIT_MESSAGE_INIT when 'struct commit_message' itself isn't? Moved
to sequencer.c now, thanks.
> Another thought. I wonder if it's possible to leave
> sequencer_parse_args() private to builtin/revert.c, making the split
> a little more logical:
Yes, I'd like this too. However, there are two new issues:
revert_or_cherry_pick_usage and action_name. The former has two
callsites: one in prepare_revs (in sequencer.c) and another in
parse_args (in builtin/revert.c). Unfortunately, action_name is even
more complicated to get rid of: the information from it is used all
over the place. Attempting to attack the problems one by one:
1. Make prepare_revs and walk_revs_populate_todo return errors to be
handled by callers. This is a fairly small patch that can come before
the big "code moving patch".
2. Duplicate action_name in both files. I don't think it's too
serious, and we can fix this later.
It has been enormously annoying to work with this "code moving patch":
everytime I make some changes to the earlier patches, I have to
recreate this one by hand; rebase offers no help whatsoever. After
throwing away code based on this patch several times, I learnt my
lesson and restricted my series to avoid building on this patch. I
consider this a very serious glitch* and I'm interested in fixing it.
Thoughts?
Thanks.
* We don't track renames, and I fully subscribe to that design.
However, that doesn't prevent us from building small helpers.
-- Ram
^ permalink raw reply
* Re: [PATCH 6/6] Retain caches of submodule refs
From: Heiko Voigt @ 2011-08-13 12:54 UTC (permalink / raw)
To: Michael Haggerty
Cc: git, Junio C Hamano, Jeff King, Drew Northup, Jakub Narebski
In-Reply-To: <1313188589-2330-7-git-send-email-mhagger@alum.mit.edu>
Hi,
On Sat, Aug 13, 2011 at 12:36:29AM +0200, Michael Haggerty wrote:
> diff --git a/refs.c b/refs.c
> index 8d1055d..f02cf94 100644
> --- a/refs.c
> +++ b/refs.c
...
> @@ -205,23 +208,28 @@ struct cached_refs *create_cached_refs(const char *submodule)
> */
> static struct cached_refs *get_cached_refs(const char *submodule)
> {
> - if (! submodule) {
> - if (!cached_refs)
> - cached_refs = create_cached_refs(submodule);
> - return cached_refs;
> - } else {
> - if (!submodule_refs)
> - submodule_refs = create_cached_refs(submodule);
> - else
> - /* For now, don't reuse the refs cache for submodules. */
> - clear_cached_refs(submodule_refs);
> - return submodule_refs;
> + struct cached_refs *refs = cached_refs;
> + if (! submodule)
> + submodule = "";
Maybe instead of searching for the main refs store a pointer to them
locally so you can immediately return here. That will keep the
performance when requesting the main refs the same.
If I see it correctly you are always prepending to the linked list and
in case many submodules get cached this could slow down the iteration
over the refs of the main repository.
> + while (refs) {
> + if (!strcmp(submodule, refs->name))
> + return refs;
> + refs = refs->next;
> }
> +
> + refs = create_cached_refs(submodule);
> + refs->next = cached_refs;
> + cached_refs = refs;
> + return refs;
> }
...
Cheers Heiko
^ permalink raw reply
* Re: [PATCH 1/6] revert: Don't remove the sequencer state on error
From: Ramkumar Ramachandra @ 2011-08-13 12:33 UTC (permalink / raw)
To: Jonathan Nieder
Cc: Git List, Junio C Hamano, Christian Couder, Daniel Barkalow,
Jeff King
In-Reply-To: <20110811192047.GE2277@elie.gateway.2wire.net>
Hi Jonathan,
Jonathan Nieder writes:
> Why bother,
> when the behavior is suppressed altogether later in the series?
Actually, this patch helped me while debugging: I'd originally
intended for it to go into 'maint'. Things have changed though- the
'sequencer-stable' is close to hitting 'next', and this series seems
to be close behind*; I'll drop this patch altogether during the
re-roll.
Thanks for making me explain this :)
-- Ram
^ permalink raw reply
* Re: [PATCH 0/6] Retain caches of submodule refs
From: Heiko Voigt @ 2011-08-13 12:34 UTC (permalink / raw)
To: Michael Haggerty
Cc: git, Junio C Hamano, Jeff King, Drew Northup, Jakub Narebski
In-Reply-To: <1313188589-2330-1-git-send-email-mhagger@alum.mit.edu>
Hi,
On Sat, Aug 13, 2011 at 12:36:23AM +0200, Michael Haggerty wrote:
> ...and work towards storing refs hierarchically.
Nice stuff!
Cheers Heiko
^ permalink raw reply
* Re: [PATCH 07/11] object: try naive cuckoo hashing
From: George Spelvin @ 2011-08-13 10:22 UTC (permalink / raw)
To: gitster; +Cc: git, linux
I had vague memories of hearing about cuckoo hashing in the pasr, but
your posting inspired me to read up on it.
Your implementation doesn't quite match the standard one. Did you get
it from somewhere, or is it your own creation?
In the classical design, the H1 and H2 hashes use two separate hash
tables (T1 and T2), so there is never any question about where insertion
should happen.
It's
- New items are inserted into T1 (at H1).
- If the slot is full, the new item is still stored there, but
it is bumped to T2.
- If that T2 slot is full, it is still overwritten, but what was there
is bumped back to T1.
etc., until a NULL pointer is found or
You use a single hash table. Is that variant analyzed somewhere, or is
it something you've found is better?
It seems that what your insert_obj_hash does is "if the H1 slot is open,
store there. Otherwise, store in the H2 slot and bump the item already
there (if any)." What this means is that as soon as you hit an object
already in its H2 slot, the insert will fall into an infinite loop and
eventually fail.
The original scheme could bump items out of H2 slots back to H1 slots.
Another advantage of the 2-table system is that every object hash two
possible homes, even if H1 == H2. With one table, the hash functions
are twice as big, so the chance of that happening is cut in half, but
such objects have only one possible home and really gum up the works.
(You could define H2 = H1 + obj->sha1[1] % (obj_hash_size-1) to
solve this, using the standard shift-and-add optimizations for
computing modulo a power of two less one, but I'm still not sure
if it's worth it.)
Another technique for using a hash table at a high load factor is
multiple-entry buckets. This is discussed in "A cool and practical
alternative to traditional hash tables"
http://www.ru.is/faculty/ulfar/CuckooHash.pdf
Because a bucket is a single cache line, accessing it adds no more
overhead than a single-entry bicket, *as long as you can validate the
lookup without following a pointer*.
The best way to do that is to store some additional validation data
(fortunately, SHA-1 provides lots; even if you're using all 5 words,
their sum is available) in the hash table itself. This does make the
table larger, but speeds up lookups.
One way to speed up pointer-bumping in the 2-hash case would be to
store H1+H2 (the full 32-bit sum) as a validation value. In addition to
allowing you to avoid following the pointer on misses the vast majority
of the time, this also lets you bump pointers from H1 to H2 without
actually following them. You know one of the hashes (because you found
the pointer in that table slot), and a subtraction produces the other.
This produces insert code like the following:
struct obj_hash_entry {
struct object *obj;
uint32_t hash_sum;
} *obj_hash;
static struct object *insert_obj_hash(struct object *obj)
{
uint32_t hash_sum = hash_val(obj->sha1);
unsigned ix = hash_sum & (obj_hash_size - 1);
unsigned n = 0, lim = 1;
unsigned loop_check; /* Ignore GCC warning */
hash_sum += hash_val(obj->sha1 + 4)
do {
struct object *tmp_obj = obj_hash[ix].obj;
uint32_t tmp_hash_sum = obj_hash[ix].hash_sum;
obj_hash[ix].obj = obj;
obj_hash[ix].hash_sum = hash_sum;
/* Brent's cycle-finding algorithm */
if (++n == lim) { /* Less registers: if (n & (n-1)) == 0 */
loop_check = ix;
lim *= 2;
}
obj = tmp_obj;
hash_sum = tmp_hash_sum;
ix = (tmp_hash_sum - ix) & (obj_hash_size - 1);
} while (obj && ix != loop_check);
return obj;
}
I presume the optimization to lookup_object is obvious.
^ permalink raw reply
* Re: [PATCHv2 27/56] string-list: Add API to remove an item from an unsorted list
From: Johannes Sixt @ 2011-08-13 9:08 UTC (permalink / raw)
To: Elijah Newren; +Cc: gitster, git, Jim Foucar
In-Reply-To: <CABPp-BFsqDhVnxDa9u3tV0yZky_az0MTCT_N5y+Oqm84+fOyvQ@mail.gmail.com>
Am 13.08.2011 00:14, schrieb Elijah Newren:
> On Fri, Aug 12, 2011 at 1:00 AM, Johannes Sixt <j.sixt@viscovery.net> wrote:
>> Am 8/12/2011 7:20, schrieb Elijah Newren:
>>> Here's an attempt for a delete_item API (note: only compile-tested).
>>
>> Seriously? You haven't even tested this patch, and still don't mark it
>> with RFC?
> ...
> However, I am unclear what you mean by not even testing the patch,
> though. I couldn't find any unit-test harness or any other kind of
> testsuite for the string_list API. I did review the code to make sure
> it looked right to me, added a use of your new function, and ran the
> standard testsuite in addition to my "re-merge all merges from
> git.git" testcase. I even single stepped through the code in a
> debugger for good measure. What testing did you want to see in
> particular?
This kind of testing is fine. And I appologize for asking a provocative
question. Of course, I know that you did test the new function suitably,
otherwise you wouldn't have submitted the series.
So, the question is rather, why did that sentence remain in the commit
message? The commit message should not be deceptive (and in particular
not blindly copy-pasted from an email that throws out a patch in the
hopes that somebody picks it up and massages into a good shape - I
thought it was clear that my patch was not a proper patch submission).
Think about someone browses history constrained by pathspec
'string-list.c'. This person will see this commit without any hint about
the merge-recursive series or that the new API is used in the next
commit, and will have to ask: "Why the heck is did someone introduce
this code and didn't even test it?"
-- Hannes
^ permalink raw reply
* can we have @{U} as an alias for @{u}
From: Sitaram Chamarty @ 2011-08-13 7:57 UTC (permalink / raw)
To: Git Mailing List
Would be so much faster to type if uppercase U were also allowed...
--
Sitaram
^ permalink raw reply
* Re: [PATCH v3 1/2] rev-parse: add option --is-well-formed-git-dir [path]
From: Heiko Voigt @ 2011-08-13 6:13 UTC (permalink / raw)
To: Nguyen Thai Ngoc Duy; +Cc: Fredrik Gustafsson, git, jens.lehmann, gitster
In-Reply-To: <CACsJy8D7W54w3ji6foXySCuvNLLBu=FY70z8+kB5hmJT_-3yCg@mail.gmail.com>
Hi,
On Sat, Aug 13, 2011 at 09:49:56AM +0700, Nguyen Thai Ngoc Duy wrote:
> On Sat, Aug 13, 2011 at 2:55 AM, Fredrik Gustafsson <iveqy@iveqy.com> wrote:
> \> +--is-well-formed-git-dir [path]::
> > + ?? ?? ?? Check if [path] is a valid git-dir or a git-file pointing to a valid
> > + ?? ?? ?? git-dir. If [path] is a valid git-dir the resolved path to git-dir will
> > + ?? ?? ?? be printed.
>
> May I suggest --is-valid-git-dir?
While we are talking about names how about:
--resolve-git-dir
? Since we had this information already the option prints out the found
resolved git directory and could be used for that.
Cheers Heiko
^ permalink raw reply
* Re: [PATCH v3 1/2] rev-parse: add option --is-well-formed-git-dir [path]
From: Nguyen Thai Ngoc Duy @ 2011-08-13 2:49 UTC (permalink / raw)
To: Fredrik Gustafsson; +Cc: git, jens.lehmann, hvoigt, gitster
In-Reply-To: <1313178913-25617-2-git-send-email-iveqy@iveqy.com>
On Sat, Aug 13, 2011 at 2:55 AM, Fredrik Gustafsson <iveqy@iveqy.com> wrote:
\> +--is-well-formed-git-dir [path]::
> + Check if [path] is a valid git-dir or a git-file pointing to a valid
> + git-dir. If [path] is a valid git-dir the resolved path to git-dir will
> + be printed.
May I suggest --is-valid-git-dir?
--
Duy
^ permalink raw reply
* Re: [PATCHv2 00/57] Re-roll of en/merge-recursive from pu
From: Elijah Newren @ 2011-08-13 2:37 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Jim Foucar
In-Reply-To: <CABPp-BE_cqtOBC_0tsy1nSOfH1XPGM0vdv9fHWp38Q0GBr7OhQ@mail.gmail.com>
On Fri, Aug 12, 2011 at 3:59 PM, Elijah Newren <newren@gmail.com> wrote:
> On Thu, Aug 11, 2011 at 11:48 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Avoiding silent mismerges is of course one of the most important criteria,
>> but we also need to make sure that a conflicted state left in the index
>> and the working tree files must not be harder to reconcile than what we
>> have been giving our users---otherwise the change will be seen as a
>> regression by them.
>
> Yeah, good point. I tried re-running my previous re-merge all merges
> in git.git testcase, modified so that when both versions of git
> reported a conflict I would compare the output of 'git ls-files -s'.
> That uncovered a regression. I think I know the fix but I need to
> retest and do some more checks.
With the new patch that I just submitted ("[PATCHv2 57/57]
merge-recursive: Don't re-sort a list whose order we depend upon"), I
now have fixed up the only issue I found with the more thorough tests
you suggest. In other words:
I used the new patch on top of my series and redid my testing. For
each two-parent merge commit in git.git (about 5000 of them), I redid
my tests. I verified that for each redone commit, both versions of
git would:
(A) EITHER both fail to merge cleanly OR both merged cleanly
(B) had identical 'git ls-files -s' output
(C) had identical output from
find . -type f -print0 | grep -z -v ^./.git | sort -z -u |
xargs -0 sha1sum
(Note that (B) is different than before; it should be useful in
comparing failed merges as well as successful ones, making sure the
contents of the index match. Also, the purpose of (C) is to ensure
that the contents of the working tree match.)
In all cases, (A) and (B) were true. There were 16 commits for which
(C) was not true; the working tree contents were different. However,
each and every such difference were due to the change in behavior to
provide more info in conflict markers (branchname:filename instead of
just branchname) -- see patch 36 in the series.
So with the new patch, and the commit message changes Johannes
suggested for patch 27, I'm hoping this series is finally in good
shape. But, as before, comments on the changes and other ideas for
more thorough testing are welcome.
^ permalink raw reply
* [PATCHv2 57/57] merge-recursive: Don't re-sort a list whose order we depend upon
From: Elijah Newren @ 2011-08-13 2:23 UTC (permalink / raw)
To: gitster; +Cc: git, Elijah Newren
In-Reply-To: <1313126429-17368-1-git-send-email-newren@gmail.com>
In record_df_conflict_files() we would resort the entries list using
df_name_compare to get a convenient ordering. Unfortunately, this broke
assumptions of the get_renames() code (via string_list_lookup() calls)
which needed the list to be in the standard ordering. When those lookups
would fail, duplicate stage_data entries could be inserted, causing the
process_renames and process_entry code to fail (in particular, a path that
that process_renames had marked as processed would still be processed
anyway in process_entry due to the duplicate entry).
Signed-off-by: Elijah Newren <newren@gmail.com>
---
Really this should just be a fixup commit to patch 23 ("merge-recursive:
Fix sorting order and directory change assumptions"), but that has some
(minor) contextual conflicts, which would require me to resubmit the
whole 50+ patch-series again. I've already flooded everyone's inboxes
enough, so I just created an extra patch.
merge-recursive.c | 16 ++++++++++++----
1 files changed, 12 insertions(+), 4 deletions(-)
diff --git a/merge-recursive.c b/merge-recursive.c
index 05ba41c..04f3c93 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -402,6 +402,7 @@ static void record_df_conflict_files(struct merge_options *o,
* and the file need to be present, then the D/F file will be
* reinstated with a new unique name at the time it is processed.
*/
+ struct string_list df_sorted_entries;
const char *last_file = NULL;
int last_len = 0;
int i;
@@ -414,14 +415,20 @@ static void record_df_conflict_files(struct merge_options *o,
return;
/* Ensure D/F conflicts are adjacent in the entries list. */
- qsort(entries->items, entries->nr, sizeof(*entries->items),
+ memset(&df_sorted_entries, 0, sizeof(struct string_list));
+ for (i = 0; i < entries->nr; i++) {
+ struct string_list_item *next = &entries->items[i];
+ string_list_append(&df_sorted_entries, next->string)->util =
+ next->util;
+ }
+ qsort(df_sorted_entries.items, entries->nr, sizeof(*entries->items),
string_list_df_name_compare);
string_list_clear(&o->df_conflict_file_set, 1);
- for (i = 0; i < entries->nr; i++) {
- const char *path = entries->items[i].string;
+ for (i = 0; i < df_sorted_entries.nr; i++) {
+ const char *path = df_sorted_entries.items[i].string;
int len = strlen(path);
- struct stage_data *e = entries->items[i].util;
+ struct stage_data *e = df_sorted_entries.items[i].util;
/*
* Check if last_file & path correspond to a D/F conflict;
@@ -449,6 +456,7 @@ static void record_df_conflict_files(struct merge_options *o,
last_file = NULL;
}
}
+ string_list_clear(&df_sorted_entries, 0);
}
struct rename {
--
1.7.6.100.g7c63c.dirty
^ permalink raw reply related
* Re: Linux Kernel + GIT SCM
From: Jakub Narebski @ 2011-08-13 0:01 UTC (permalink / raw)
To: Vecu BOSSEUR; +Cc: git
In-Reply-To: <CACivvv1-UcZdOx+ThLuUkqwL=oy7aETckV+18Fpj_zoXkcXJWQ@mail.gmail.com>
Vecu BOSSEUR <vecu.bosseur@gmail.com> writes:
> Hello,
>
> I need GIT SCM to allow me to suspend an operation and to resume it
> later : initial cloning, synchronizing repositories, ...
>
> I believed this was the purpose of the "GIT Sequencer" feature
> developped at 2011 Google Summmer Of Code ; please, tell me if I
> missed something.
>
> And I would like to know whether "kernel.org" servers will support
> this feature soon or not.
No, "Git sequencer" has nothing to do with resumable (and suspendable)
clone, fetch or push. Resumable transport is not implemented, and it
looks like ti would be difficult to add.
The sequencer project is about engine that it is to be used by rebase,
multiple cherry-pick, multiple revert, and git-am. Among others it is
meant to increase consistency between those commands.
--
Jakub Narębski
^ permalink raw reply
* [PATCH 6/6] Retain caches of submodule refs
From: Michael Haggerty @ 2011-08-12 22:36 UTC (permalink / raw)
To: git
Cc: Junio C Hamano, Jeff King, Drew Northup, Jakub Narebski,
Michael Haggerty
In-Reply-To: <1313188589-2330-1-git-send-email-mhagger@alum.mit.edu>
Instead of keeping track of one cache for refs in the main repo and
another single cache shared among submodules, keep a linked list of
cached_refs objects, one for each module/submodule. Change
invalidate_cached_refs() to invalidate all caches. (Previously, it
only invalidated the cache of the main repo because the submodule
caches were not reused anyway.)
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
refs.c | 34 +++++++++++++++++++++-------------
1 files changed, 21 insertions(+), 13 deletions(-)
diff --git a/refs.c b/refs.c
index 8d1055d..f02cf94 100644
--- a/refs.c
+++ b/refs.c
@@ -153,13 +153,15 @@ static struct ref_list *sort_ref_list(struct ref_list *list)
* when doing a full libification.
*/
static struct cached_refs {
+ struct cached_refs *next;
char did_loose;
char did_packed;
struct ref_list *loose;
struct ref_list *packed;
/* The submodule name, or "" for the main repo. */
char name[FLEX_ARRAY];
-} *cached_refs, *submodule_refs;
+} *cached_refs;
+
static struct ref_list *current_ref;
static struct ref_list *extra_refs;
@@ -191,6 +193,7 @@ struct cached_refs *create_cached_refs(const char *submodule)
submodule = "";
len = strlen(submodule) + 1;
refs = xmalloc(sizeof(struct cached_refs) + len);
+ refs->next = NULL;
refs->did_loose = refs->did_packed = 0;
refs->loose = refs->packed = NULL;
memcpy(refs->name, submodule, len);
@@ -205,23 +208,28 @@ struct cached_refs *create_cached_refs(const char *submodule)
*/
static struct cached_refs *get_cached_refs(const char *submodule)
{
- if (! submodule) {
- if (!cached_refs)
- cached_refs = create_cached_refs(submodule);
- return cached_refs;
- } else {
- if (!submodule_refs)
- submodule_refs = create_cached_refs(submodule);
- else
- /* For now, don't reuse the refs cache for submodules. */
- clear_cached_refs(submodule_refs);
- return submodule_refs;
+ struct cached_refs *refs = cached_refs;
+ if (! submodule)
+ submodule = "";
+ while (refs) {
+ if (!strcmp(submodule, refs->name))
+ return refs;
+ refs = refs->next;
}
+
+ refs = create_cached_refs(submodule);
+ refs->next = cached_refs;
+ cached_refs = refs;
+ return refs;
}
static void invalidate_cached_refs(void)
{
- clear_cached_refs(get_cached_refs(NULL));
+ struct cached_refs *refs = cached_refs;
+ while (refs) {
+ clear_cached_refs(refs);
+ refs = refs->next;
+ }
}
static struct ref_list *read_packed_refs(FILE *f)
--
1.7.6.8.gd2879
^ permalink raw reply related
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox