* [BUG] imap-send.c fails to build on OSX
From: Randal L. Schwartz @ 2006-03-12 14:44 UTC (permalink / raw)
To: git
gcc -o imap-send.o -c -g -O2 -Wall -I/sw/include -I/opt/local/include -DSHA1_HEADER='<openssl/sha.h>' imap-send.c
imap-send.c:376: error: static declaration of 'vasprintf' follows non-static declaration
/usr/include/stdio.h:297: error: previous declaration of 'vasprintf' was here
make: *** [imap-send.o] Error 1
--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<merlyn@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
^ permalink raw reply
* Re: [PATCH] Use explicit pointers for execl...() sentinels.
From: Timo Hirvonen @ 2006-03-12 15:13 UTC (permalink / raw)
To: git; +Cc: git
In-Reply-To: <slrne18aae.fr9.mdw@metalzone.distorted.org.uk>
On Sun, 12 Mar 2006 13:59:42 +0000 (UTC)
Mark Wooding <mdw@distorted.org.uk> wrote:
> A terminator of `0' (or `NULL', which might well expand to `0') gets
> passed as type `int' in the absence of argument type declarations (which
> is the case for execl...(), since it uses varargs). Argument passing
> conventions may differ between `int' and `char *' if, say, `int' is 32
> bits and pointers a 64; and there's no particular guarantee that a null
> pointer has all-bits-zero anyway.
NULL should always be ((void *)0). What 64-bit systems declare NULL as
plain 0 (not 0L)? How about fixing those systems instead of making the
git source code unreadable.
--
http://onion.dynserv.net/~timo/
^ permalink raw reply
* Re: [PATCH] Trivial warning fix for imap-send.c
From: Linus Torvalds @ 2006-03-12 16:57 UTC (permalink / raw)
To: Mark Wooding; +Cc: git
In-Reply-To: <slrne17urp.fr9.mdw@metalzone.distorted.org.uk>
On Sun, 12 Mar 2006, Mark Wooding wrote:
> "Art Haas" <ahaas@airmail.net> wrote:
>
> > - execl( "/bin/sh", "sh", "-c", srvc->tunnel, 0 );
> > + execl( "/bin/sh", "sh", "-c", srvc->tunnel, NULL );
>
> This is not the right fix. NULL can be simply a #define for 0 (see
> 6.3.2.3#3 and 7.17). You need to write (char *)0 or (char *)NULL. I
> prefer to avoid the macro NULL entirely, since its misleading behaviour
> is precisely what got us into this mess.
It's perfectly fine.
Quite frankly, if you have a 64-bit C compiler that doesn't make "NULL" be
"((void *)0)" (or equivalent - some compilers will actually have NULL as
an intrisic, because especially if they also support C++, NULL has some
really magical properties there), you should switch vendors as quickly as
humanly possible.
The "#define NULL 0" practice is still _legal_ C, but that doesn't make it
any less broken. It's K&R traditional, but git requires ANSI prototypes
and some fancy features from modern compilers, so K&R compilers aren't
welcome anyway, and if their headers don't define NULL as a void pointer,
their headers are simply _broken_.
So in modern C, using NULL at the end of a varargs array as a pointer is
perfectly sane, and the extra cast is just ugly and bowing to bad
programming practices and makes no sense to anybody who never saw the
horror that is K&R.
It's akin to trying to not using prototypes, or to trying to limit your
externally visible names to 7 characters. It was "appropriate" about two
decades ago, these days it's just cuddling broken setups that have been
broken for a long long time.
Btw, the reason NULL _has_ to be a pointer ("((void *)0)" or otherwise) is
simply that if it isn't, you not only won't get reasonable varargs
behaviour, you'll also miss real warnings. I've seen broken code like
int i = NULL;
in my life, and if the compiler doesn't warn about that, then the compiler
is BROKEN, and not worth supporting as a programmer.
Linus
^ permalink raw reply
* Re: git-diff-tree -M performance regression in 'next'
From: Linus Torvalds @ 2006-03-12 17:00 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Fredrik Kuivinen, git
In-Reply-To: <7voe0bdeyr.fsf@assigned-by-dhcp.cox.net>
On Sun, 12 Mar 2006, Junio C Hamano wrote:
>
> On my otherwise idle Duron 750 with slow disks, I am getting
> something like these:
>
> 0.99.9m : 130m virtual, 40m resident, (0major+14205minor)
> 67.62user 0.08system 1:15.95elapsed
> master : 130m virtual, 40m resident, (0major+12510minor)
> 66.06user 0.07system 1:10.95elapsed
> "next" : 150m virtual, 65m resident, (0major+49858minor)
> 51.41user 0.45system 0.57.55elapsed
Any way to fix that "4 times as many page misses, and 70% bigger rss?"
thing? It looks like you're not very careful about your memory use.
I realize that git in general wants a lot of memory, but I see that as a
failure most of the time. I've got 2GB in most of my machines, but I
shouldn't _need_ to have it..
Linus
^ permalink raw reply
* Re: [PATCH] Use explicit pointers for execl...() sentinels.
From: Mark Wooding @ 2006-03-12 17:32 UTC (permalink / raw)
To: git
In-Reply-To: <20060312171316.39d138f8.tihirvon@gmail.com>
Timo Hirvonen <tihirvon@gmail.com> wrote:
> NULL should always be ((void *)0).
Says who? I already gave chapter and verse for what NULL is required to
do.
Besides, (void *)0 fixes /this particular/ problem, because `void *' and
`char *' have the same representation (6.2.5#27). This wouldn't help us
with a putative function which takes an arbitrary number of `foo *'
pointers, since nothing guarantees that `void *' and `foo *' have
similar representations. You'd have to say `(foo *)0' or `(foo *)NULL'.
> What 64-bit systems declare NULL as plain 0 (not 0L)?
Don't know: didn't look. 0L won't do the right thing with IL32LLP64, if
anyone was actually crazy enough to specify such an ABI. The point is,
there's not much
> How about fixing those systems instead of making the git source code
> unreadable.
Because, according to the C and POSIX specs, they're not wrong.
The right fix from the point of view of a C implementation would be to
define NULL to be some weird __null_pointer token which the compiler
could warn about whenever it was used in an untyped argument context.
(Besides, I don't find bare or casted `0' unreadable. Maybe I'm just
strange.)
-- [mdw]
^ permalink raw reply
* Re: [PATCH] Trivial warning fix for imap-send.c
From: Mark Wooding @ 2006-03-12 18:01 UTC (permalink / raw)
To: git
In-Reply-To: <Pine.LNX.4.64.0603120847500.3618@g5.osdl.org>
Linus Torvalds <torvalds@osdl.org> wrote:
> So in modern C, using NULL at the end of a varargs array as a pointer is
> perfectly sane, and the extra cast is just ugly and bowing to bad
> programming practices and makes no sense to anybody who never saw the
> horror that is K&R.
No! You can still get bitten. You're lucky that on common platforms
all pointers look the same, but if you find one where `char *' (and
hence `void *') isn't the same as `struct foo *' then, under appropriate
circumstances you /will/ unless you put the casts in.
Now, maybe we don't care for GIT. That's your (and Junio's) call. My
natural approach is to work as closely as I can to the specs (and then
throw in hacks for platforms which /still/ don't work), though, which is
why I brought the subject up.
-- [mdw]
^ permalink raw reply
* Re: [PATCH] Use explicit pointers for execl...() sentinels.
From: Timo Hirvonen @ 2006-03-12 18:08 UTC (permalink / raw)
To: git; +Cc: git
In-Reply-To: <slrne18mq3.fr9.mdw@metalzone.distorted.org.uk>
On Sun, 12 Mar 2006 17:32:51 +0000 (UTC)
Mark Wooding <mdw@distorted.org.uk> wrote:
> Besides, (void *)0 fixes /this particular/ problem, because `void *' and
> `char *' have the same representation (6.2.5#27). This wouldn't help us
> with a putative function which takes an arbitrary number of `foo *'
> pointers, since nothing guarantees that `void *' and `foo *' have
> similar representations. You'd have to say `(foo *)0' or `(foo *)NULL'.
NULL pointer does not point to any data, it just says it's 'empty'. So
it doesn't need to be same type pointer as specified in the function
prototype. Pointers are just addresses, it doesn't matter from to code
generation point of view whether it is (char *)0 or (void *)0.
> Don't know: didn't look. 0L won't do the right thing with IL32LLP64, if
> anyone was actually crazy enough to specify such an ABI. The point is,
> there's not much
sizeof(unsigned long) is sizeof(void *) in real world.
> > How about fixing those systems instead of making the git source code
> > unreadable.
>
> Because, according to the C and POSIX specs, they're not wrong.
They didn't think of 64-bit architectures back then, I suppose.
> The right fix from the point of view of a C implementation would be to
> define NULL to be some weird __null_pointer token which the compiler
> could warn about whenever it was used in an untyped argument context.
In practice (void *)0 is good enough.
> (Besides, I don't find bare or casted `0' unreadable. Maybe I'm just
> strange.)
'ugly' would have been better word than 'unreadable'.
--
http://onion.dynserv.net/~timo/
^ permalink raw reply
* Re: [BUG] imap-send.c fails to build on OSX
From: Randal L. Schwartz @ 2006-03-12 19:08 UTC (permalink / raw)
To: git
In-Reply-To: <863bhnlo3r.fsf@blue.stonehenge.com>
>>>>> "Randal" == Randal L Schwartz <merlyn@stonehenge.com> writes:
Randal> gcc -o imap-send.o -c -g -O2 -Wall -I/sw/include -I/opt/local/include -DSHA1_HEADER='<openssl/sha.h>' imap-send.c
Randal> imap-send.c:376: error: static declaration of 'vasprintf' follows non-static declaration
Randal> /usr/include/stdio.h:297: error: previous declaration of 'vasprintf' was here
Randal> make: *** [imap-send.o] Error 1
By the way, /usr/include/stdio.h near the line in question looks like:
int vasprintf(char **, const char *, va_list) __DARWIN_LDBL_COMPAT(vasprintf);
--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<merlyn@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
^ permalink raw reply
* Re: [PATCH] Trivial warning fix for imap-send.c
From: A Large Angry SCM @ 2006-03-12 19:20 UTC (permalink / raw)
To: Mark Wooding; +Cc: git
In-Reply-To: <slrne18of5.fr9.mdw@metalzone.distorted.org.uk>
Mark Wooding wrote:
> Linus Torvalds <torvalds@osdl.org> wrote:
>
>>So in modern C, using NULL at the end of a varargs array as a pointer is
>>perfectly sane, and the extra cast is just ugly and bowing to bad
>>programming practices and makes no sense to anybody who never saw the
>>horror that is K&R.
>
> No! You can still get bitten. You're lucky that on common platforms
> all pointers look the same, but if you find one where `char *' (and
> hence `void *') isn't the same as `struct foo *' then, under appropriate
> circumstances you /will/ unless you put the casts in.
Please explain how malloc() can work on such a platform. My reading of
the '89 ANSI C spec. finds that _ALL_ (non function) pointers _are_
cast-able to/from a void * and that NULL should be #defined as (void *).
See 3.2.2.3 and 4.1.5 if interested.
^ permalink raw reply
* Re: git-diff-tree -M performance regression in 'next'
From: Junio C Hamano @ 2006-03-12 19:34 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Fredrik Kuivinen, git
In-Reply-To: <Pine.LNX.4.64.0603120858230.3618@g5.osdl.org>
Linus Torvalds <torvalds@osdl.org> writes:
> On Sun, 12 Mar 2006, Junio C Hamano wrote:
>>
>> master : 130m virtual, 40m resident, (0major+12510minor)
>> 66.06user 0.07system 1:10.95elapsed
>> "next" : 150m virtual, 65m resident, (0major+49858minor)
>> 51.41user 0.45system 0.57.55elapsed
>
> Any way to fix that "4 times as many page misses, and 70% bigger rss?"
> thing? It looks like you're not very careful about your memory use.
I started from "80 times as many page misses and 5 times bigger
rss", shrunk it down to the above after doing more careful
memory use, running out of ideas to shrink it more, and pushed
it out. So...
^ permalink raw reply
* Re: Any news on an Eclipse plugin?
From: lamikr @ 2006-03-12 19:50 UTC (permalink / raw)
To: Noel Grandin; +Cc: Shawn Pearce, git
In-Reply-To: <440D2F4E.9090009@peralex.com>
Hi
Have you yet made any kind of planning of the features that would be
available or put up the repository?
I use novadays Eclipse basically for all of my editing and something
like CVS/Subclipse plug-ins for git would be cool.
(cdt cross-indexing is still a little bit slow with the amount of files
in kernel so with kernel I have turned that off)
Noel Grandin wrote:
>The subversion plugin (subclipse.tigris.org) might be a good starting
>point since it delegates a lot of it's low-level work through an
>interface called svnClientAdapter. Re-implementing that to talk to git
>should get you something useful in a reasonable time-frame.
>
>Note that an eclipse team plugin is a pretty complicated beast.
>
>
Yes, but very powerfull for the people like me who have who just have
never bothered to learn VI/Emacs/sed properly
and feel with them like having 5 thumps, code finders, search tools,
refactoring tools, etc. available in Eclipse are very cool.
So if the repository for git plug-ins goes up somewhere I could try to
help a little bit.
Mika
^ permalink raw reply
* Re: Possible --remove-empty bug
From: Junio C Hamano @ 2006-03-12 21:31 UTC (permalink / raw)
To: Marco Costalba; +Cc: git, Linus Torvalds
In-Reply-To: <e5bfff550603120612k555fc7f3v9d8d17b1bd0b9e41@mail.gmail.com>
"Marco Costalba" <mcostalba@gmail.com> writes:
>>>From git-rev-list documentation:
>
> --remove-empty::
> Stop when a given path disappears from the tree.
>
> But isn't it to be intended *after* a path disapperas from the tree?
To be honest, I do not know how --remove-empty is intended to
work. What revision traversal code does and what the above says
are different.
The traversal code goes like this:
* Start from given commits (both interesting and
uninteresting), look at still-to-be-procesed commit
one by one, by calling add_parents_to_list().
* add_parents_to_list() grows still-to-be-processed
list; if the current commit is uninteresting, mark its
parents also uninteresting, and if no interesting
commit remains in the still-to-be-processed list, we
are done. On the other hand, if the current commit is
interesting, place it to the list of results.
* After the above traversal is done, the consumer calls
get_revision() to retrieve commits from the list of
results one-by-one. We return only interesting ones.
And in add_parents_to_list()
* if the commit is interesting, and when we are limiting
by paths, we call try_to_simplify_commit(). This
checks if the tree associated with the current commit
is the same as one of its parents' with respect to
specified paths, and if so pretend that the current
commit has only that parent and no other. This can
make a merge commit to lose other parents that we do
not inherit the specified paths from.
* try_to_simplify_commit() looks at each parent, and:
- if we find a parent that has the same tree (wrt the
paths we are interested in), we pretend it is the
sole parent of this commit.
- if we find a parent that does not have any of the
specified paths, we pretend we do not have that
parent under --remove-empty.
- otherwise we do not munge the list of parents.
My understanding of what the code is doing from the above
reading is to lose that empty parent, and it does not have much
to do with stop traversing the ancestry chain at such commit. I
am not sure that is what was intended...
Maybe something like this is closer to what the documentation
says.
-- >8 --
diff --git a/revision.c b/revision.c
index c8d93ff..03085ff 100644
--- a/revision.c
+++ b/revision.c
@@ -315,9 +315,14 @@ static void try_to_simplify_commit(struc
return;
case TREE_NEW:
- if (revs->remove_empty_trees && same_tree_as_empty(p->tree)) {
- *pp = parent->next;
- continue;
+ if (revs->remove_empty_trees &&
+ same_tree_as_empty(p->tree)) {
+ /* We are adding all the specified paths from
+ * this parent, so the parents of it is
+ * not interesting, but the difference between
+ * this parent and us still is interesting.
+ */
+ p->object.flags |= UNINTERESTING;
}
/* fallthrough */
case TREE_DIFFERENT:
^ permalink raw reply related
* Re: Possible --remove-empty bug
From: Linus Torvalds @ 2006-03-12 22:54 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Marco Costalba, git
In-Reply-To: <7vk6azz6xx.fsf@assigned-by-dhcp.cox.net>
On Sun, 12 Mar 2006, Junio C Hamano wrote:
>
> To be honest, I do not know how --remove-empty is intended to
> work.
It's supposed to stop traversing the tree once a pathname disappears.
> Maybe something like this is closer to what the documentation
> says.
If it is, then the documentation is broken.
The fact that a pathname disappears does _not_ make the commit
uninteresting. It just means that we should stop traversing that parent.
"uninteresting" has a big side effect: it inherits to parents. So if you
have
a
/ \
b c
\ /
d
where the pathname disappeared in "b", you must NOT mark it uninteresting,
because that would mean that "d" is also uninteresting.
There's a huge difference between saying "I will not traverse down this
line any more" and "I mark this commit uninteresting". The first one just
stops adding commits to the commit list (but parents deeper down might
still be interesting because they are also reached through another
pathway). The second says "this commit and all of its ancestors are
deemed worthless".
The "path goes away" case is meant to just stop traversal, not mark all
parents worthless.
Linus
^ permalink raw reply
* Re: [PATCH] Trivial warning fix for imap-send.c
From: Linus Torvalds @ 2006-03-12 23:02 UTC (permalink / raw)
To: Mark Wooding; +Cc: git
In-Reply-To: <slrne18of5.fr9.mdw@metalzone.distorted.org.uk>
On Sun, 12 Mar 2006, Mark Wooding wrote:
> Linus Torvalds <torvalds@osdl.org> wrote:
>
> > So in modern C, using NULL at the end of a varargs array as a pointer is
> > perfectly sane, and the extra cast is just ugly and bowing to bad
> > programming practices and makes no sense to anybody who never saw the
> > horror that is K&R.
>
> No! You can still get bitten. You're lucky that on common platforms
> all pointers look the same, but if you find one where `char *' (and
> hence `void *') isn't the same as `struct foo *' then, under appropriate
> circumstances you /will/ unless you put the casts in.
Not relevant. Show me any system that matters.
The fact is, compilers should conform to programmers, not the other way
around. Bending over backwards for broken systems is _wrong_. The fact
that there are insane build environments doesn't excuse bad manners, and
explicit casts that aren't needed are HORRIBLE manners.
There is no valid reason to _ever_ cast NULL pointers.
Btw, the same goes for casting the result from malloc etc, which some
people also do.
Put another way: you should not encourage insane systems, and you should
definitely NOT encourage nit-picking people who read the standards in
insane ways and say that the standards _allow_ badly behaved build
environments.
It's true that the standards _allow_ crazy build environments. Who the
f*ck cares? Crazy and bad build environments aren't any better for being
allowed by the standard. Screw them. Call them names. And refuse to work
with them.
Linus
^ permalink raw reply
* Re: git-diff-tree -M performance regression in 'next'
From: Junio C Hamano @ 2006-03-13 0:42 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Fredrik Kuivinen, git
In-Reply-To: <7vk6azcv9y.fsf@assigned-by-dhcp.cox.net>
> Linus Torvalds <torvalds@osdl.org> writes:
>
>> On Sun, 12 Mar 2006, Junio C Hamano wrote:
>>>
>>> master : 130m virtual, 40m resident, (0major+12510minor)
>>> 66.06user 0.07system 1:10.95elapsed
>>> "next" : 150m virtual, 65m resident, (0major+49858minor)
>>> 51.41user 0.45system 0.57.55elapsed
>>
>> Any way to fix that "4 times as many page misses, and 70% bigger rss?"
>> thing? It looks like you're not very careful about your memory use.
"this" : 145m virtual, 57m resident, (0major+18855minor)
39.81user 0.28system 0:42.16elapsed
50% more page misses, 45% bigger rss, 65% less usertime.
Slowly getting there...
-- >8 --
[PATCH] diffcore-delta: make the hash a bit denser.
To reduce wasted memory, wait until the hash fills up more
densely before we rehash. This reduces the working set size a
bit further.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
diffcore-delta.c | 13 +++++++++----
diffcore-rename.c | 4 +++-
2 files changed, 12 insertions(+), 5 deletions(-)
af0b459589edaa77c51a892dd7dc44329634d253
diff --git a/diffcore-delta.c b/diffcore-delta.c
index 471b98f..f8a7518 100644
--- a/diffcore-delta.c
+++ b/diffcore-delta.c
@@ -25,8 +25,12 @@
*/
/* Wild guess at the initial hash size */
-#define INITIAL_HASH_SIZE 10
+#define INITIAL_HASH_SIZE 9
#define HASHBASE 65537 /* next_prime(2^16) */
+/* We leave more room in smaller hash but do not let it
+ * grow to have unused hole too much.
+ */
+#define INITIAL_FREE(sz_log2) ((1<<(sz_log2))*(sz_log2-3)/(sz_log2))
struct spanhash {
unsigned long hashval;
@@ -38,7 +42,8 @@ struct spanhash_top {
struct spanhash data[FLEX_ARRAY];
};
-static struct spanhash *spanhash_find(struct spanhash_top *top, unsigned long hashval)
+static struct spanhash *spanhash_find(struct spanhash_top *top,
+ unsigned long hashval)
{
int sz = 1 << top->alloc_log2;
int bucket = hashval & (sz - 1);
@@ -62,7 +67,7 @@ static struct spanhash_top *spanhash_reh
new = xmalloc(sizeof(*orig) + sizeof(struct spanhash) * sz);
new->alloc_log2 = orig->alloc_log2 + 1;
- new->free = osz;
+ new->free = INITIAL_FREE(new->alloc_log2);
memset(new->data, 0, sizeof(struct spanhash) * sz);
for (i = 0; i < osz; i++) {
struct spanhash *o = &(orig->data[i]);
@@ -122,7 +127,7 @@ static struct spanhash_top *hash_chars(u
i = INITIAL_HASH_SIZE;
hash = xmalloc(sizeof(*hash) + sizeof(struct spanhash) * (1<<i));
hash->alloc_log2 = i;
- hash->free = (1<<i)/2;
+ hash->free = INITIAL_FREE(i);
memset(hash->data, 0, sizeof(struct spanhash) * (1<<i));
/* an 8-byte shift register made of accum1 and accum2. New
diff --git a/diffcore-rename.c b/diffcore-rename.c
index b80b432..8380049 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -307,8 +307,10 @@ void diffcore_rename(struct diff_options
m->score = estimate_similarity(one, two,
minimum_score);
}
+ /* We do not need the text anymore */
free(two->cnt_data);
- two->cnt_data = NULL;
+ free(two->data);
+ two->data = two->cnt_data = NULL;
dst_cnt++;
}
/* cost matrix sorted by most to least similar pair */
--
1.2.4.g3dcf
^ permalink raw reply related
* Re: Possible --remove-empty bug
From: Junio C Hamano @ 2006-03-13 1:08 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Marco Costalba, git
In-Reply-To: <Pine.LNX.4.64.0603121450210.3618@g5.osdl.org>
Linus Torvalds <torvalds@osdl.org> writes:
> On Sun, 12 Mar 2006, Junio C Hamano wrote:
>>
>> To be honest, I do not know how --remove-empty is intended to
>> work.
>
> It's supposed to stop traversing the tree once a pathname disappears.
Then what we should simplify is the parent commit that does not
have those pathnames (i.e. remove parents from that parent
commit). In other words, currently the code removes the parent
commit that makes the tree disappear, but we would want to keep
that parent, remove the grandparents, and then mark the parent
uninteresting.
-- >8 --
[PATCH] revision traversal: --remove-empty fix (take #2).
Marco Costalba reports that --remove-empty omits the commit that
created paths we are interested in. try_to_simplify_commit()
logic was dropping a parent we introduced those paths against,
which I think is not what we meant. Instead, this makes such
parent parentless.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
diff --git a/revision.c b/revision.c
index c8d93ff..73fba5d 100644
--- a/revision.c
+++ b/revision.c
@@ -315,9 +315,18 @@ static void try_to_simplify_commit(struc
return;
case TREE_NEW:
- if (revs->remove_empty_trees && same_tree_as_empty(p->tree)) {
- *pp = parent->next;
- continue;
+ if (revs->remove_empty_trees &&
+ same_tree_as_empty(p->tree)) {
+ /* We are adding all the specified
+ * paths from this parent, so the
+ * history beyond this parent is not
+ * interesting. Remove its parents
+ * (they are grandparents for us).
+ * IOW, we pretend this parent is a
+ * "root" commit.
+ */
+ parse_commit(p);
+ p->parents = NULL;
}
/* fallthrough */
case TREE_DIFFERENT:
^ permalink raw reply related
* Re: git-diff-tree -M performance regression in 'next'
From: Linus Torvalds @ 2006-03-13 1:09 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Fredrik Kuivinen, git
In-Reply-To: <7vwtezw4ye.fsf@assigned-by-dhcp.cox.net>
On Sun, 12 Mar 2006, Junio C Hamano wrote:
>
> To reduce wasted memory, wait until the hash fills up more
> densely before we rehash. This reduces the working set size a
> bit further.
Umm. Why do you rehash at all?
Just take the size of the "src" file as the initial hash size.
Also, I think it is likely really wasteful to try to actually hash at
_each_ character. Instead, let's say that the chunk-size is 8 bytes (like
you do now), and let's say that you have a 32-bit good hash of those 8
bytes. What you can do is:
- for each 8 bytes in the source, hash those 8 bytes (not every byte)
- for each byte in the other file, hash 8 next bytes. IF it matches a
hash in the source with a non-zero count, subtract the count for that
hash and move up by _eight_ characters! If it doesn't, add one to
"characters not matched" counter, and move up _one_ character, and try
again.
At the end of this, you have two counts: the count of characters that you
couldn't match in the other file, and the count of 8-byte hash-chunks that
you couldn't match in the first one. Use those two counts to decide if
it's close or not.
Especially for good matches, this should basically cut your work into an
eight of what you do now.
Actually, even for bad matches, you cut the first source overhead into one
eight (the second file will obviously do the "update by 1 byte" most of
the time).
Don't you think that would be as accurate as what you're doing now (it's
the same basic notion, after all), and noticeably faster?
Linus
^ permalink raw reply
* Re: git-diff-tree -M performance regression in 'next'
From: Junio C Hamano @ 2006-03-13 1:22 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Fredrik Kuivinen, git
In-Reply-To: <Pine.LNX.4.64.0603121700410.3618@g5.osdl.org>
Linus Torvalds <torvalds@osdl.org> writes:
> Umm. Why do you rehash at all?
>
> Just take the size of the "src" file as the initial hash size.
The code uses close to 16-bit hash and I had 65k flat array as a
hashtable. That one was what you commented as "4-times as many
page misses".
Interestingly enough, that kind of flat array representation
seems to be too sparse and gives very bad performance behaviour.
The improvement I mentioned in the message you are replying to
is the result of making it into smaller (starting at (1<<9) or
something like that) linear-overflowing hash.
The latter suggestion I need to think about it a bit more.
^ permalink raw reply
* Re: git-diff-tree -M performance regression in 'next'
From: Linus Torvalds @ 2006-03-13 1:29 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Fredrik Kuivinen, git
In-Reply-To: <Pine.LNX.4.64.0603121700410.3618@g5.osdl.org>
On Sun, 12 Mar 2006, Linus Torvalds wrote:
>
> Also, I think it is likely really wasteful to try to actually hash at
> _each_ character. Instead, let's say that the chunk-size is 8 bytes (like
> you do now), and let's say that you have a 32-bit good hash of those 8
> bytes. What you can do is:
Side note: regardless, your new algorithm clearly does seem faster.
However, it worries me a bit that you don't check the source strings,
especially since the hash you use seems somewhat suspect (why limit it to
essentially just 16 bits? Wouldn't it be best to have the _biggest_ prime
that fits in the "hashval" thing, which is at least 32 bits? Also,
shouldn't you make that spanhash thing use a "unsigned int" instead of
"unsigned long"?)
So I would suggest instead the hash function to be:
typedef unsigned long long u64;
/* Biggest prime in 32 bits */
#define HASHVAL (4294967291u)
u64 value = *(u64 *)src;
src += 8;
hash = value % 4294967291u;
which does a 64-bit modulus, but hey, 64-bit hw isn't _that_ uncommon any
more, and it's not _excessively_ slow on x86 (gcc doesn't generate good
code, but we could actually use the kernel "do_div()" routine for much
faster division of 64 % 32 than what gcc can do - since the dividend is
32-bit, you actually only need to do one 32/32 division and one 64/32
division, so the optimized hash function on a good x86 will be just in
the teens of cycles for the 64-bit modulus).
Linus
^ permalink raw reply
* Re: git-diff-tree -M performance regression in 'next'
From: Linus Torvalds @ 2006-03-13 1:31 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Fredrik Kuivinen, git
In-Reply-To: <Pine.LNX.4.64.0603121710110.3618@g5.osdl.org>
On Sun, 12 Mar 2006, Linus Torvalds wrote:
>
> u64 value = *(u64 *)src;
> src += 8;
> hash = value % 4294967291u;
Btw, this assumes the "only hash every 8 bytes" at the source, in which
case this is ok even on architectures that need aligned reads. For the
non-aligned reads, you'd need your "shift the value" approach.
Linus
^ permalink raw reply
* Re: git-diff-tree -M performance regression in 'next'
From: Linus Torvalds @ 2006-03-13 1:39 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Fredrik Kuivinen, git
In-Reply-To: <7vhd63w33n.fsf@assigned-by-dhcp.cox.net>
On Sun, 12 Mar 2006, Junio C Hamano wrote:
>
> The code uses close to 16-bit hash and I had 65k flat array as a
> hashtable. That one was what you commented as "4-times as many
> page misses".
Ahh. That explains the limited bits in the hash function too. I only
looked at the current sources, not at the historic ones.
Btw, the page misses may come from the fact that you allocated and
re-allocated the flat array all the time. That can be very expensive for
big allocations, since most libraries may decide that it's a big enough
area that it should be map/unmap'ed in order to give memory back to the
system (without realizing that there's another allocation coming soon
afterwards of the same size).
If you map/unmap, the kernel will end up having to not just use new pages,
but obviously also clear them for security reasons. So it ends up sucking
on many levels. In contrast, if you just have a 64k-entry array of "int",
and allocate it _once_ (instead of once per file-pair) you'll still have
to clear it in between file-pairs, but at least you won't have the
overhead of mapping/unmapping it.
The clearing can still be pretty expensive (64k "int" entries is 256kB,
and since most _files_ are just in the ~4-8kB range, you're spending a
_lot_ of time just memset'ing). Which is why it's probably a good idea to
instead default to having just "filesize / 8" entries, but then you can
obviously not use the hash as the index any more.
Linus
^ permalink raw reply
* Re: git-diff-tree -M performance regression in 'next'
From: Linus Torvalds @ 2006-03-13 2:29 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Fredrik Kuivinen, git
In-Reply-To: <Pine.LNX.4.64.0603121710110.3618@g5.osdl.org>
On Sun, 12 Mar 2006, Linus Torvalds wrote:
>
> So I would suggest instead the hash function to be:
>
> typedef unsigned long long u64;
>
> /* Biggest prime in 32 bits */
> #define HASHVAL (4294967291u)
>
>
> u64 value = *(u64 *)src;
> src += 8;
> hash = value % 4294967291u;
>
> which does a 64-bit modulus, but hey, 64-bit hw isn't _that_ uncommon any
> more, and it's not _excessively_ slow on x86 (gcc doesn't generate good
> code, but we could actually use the kernel "do_div()" routine for much
> faster division of 64 % 32 than what gcc can do - since the dividend is
> 32-bit, you actually only need to do one 32/32 division and one 64/32
> division, so the optimized hash function on a good x86 will be just in
> the teens of cycles for the 64-bit modulus).
Actually, on x86, where we can do the 64-by-32 division with a single
instruction, this seems to be the best possible code:
#define HASH_VAL (4294967291u)
static inline unsigned int hash64x32(unsigned long long a)
{
unsigned int high, low;
unsigned int modulus;
asm(""
:"=a" (low), "=d" (high)
:"A" (a));
if (high > HASH_VAL)
high -= HASH_VAL;
asm("divl %2"
:"=a" (low), "=d" (modulus)
:"rm" (HASH_VAL), "0" (low), "1" (high));
return modulus;
}
at least as far as I can think.
The magic is the reduction of the high 32 bits: for the general case you
want a modulus for that reduction, but since we're dividing with a
really big value, the modulus of the high bits really does end up
becoming just that simple
if (high > HASH_VAL)
high -= HASH_VAL;
and then we just need to do a single "divl" instruction.
So if you want a 32-bit hash of an 8-byte area, this should be a pretty
good and fast way to calculate it.
Of course, maybe just doing an adler32() is simpler/better. But with
the above, at least on x86, I suspect you get an even better
distribution at a lower cost (of course, different coress do differently
well on large divisions, but integer division being pretty important for
some codes, modern cores actually tend to be pretty good at it).
Linus
^ permalink raw reply
* Re: git-diff-tree -M performance regression in 'next'
From: Linus Torvalds @ 2006-03-13 2:53 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Fredrik Kuivinen, git
In-Reply-To: <Pine.LNX.4.64.0603121810140.3618@g5.osdl.org>
On Sun, 12 Mar 2006, Linus Torvalds wrote:
>
> if (high > HASH_VAL)
> high -= HASH_VAL;
That should be ">= HASH_VAL", of course. I'm a retard.
Linus
^ permalink raw reply
* Re: [PATCH] Trivial warning fix for imap-send.c
From: H. Peter Anvin @ 2006-03-13 2:59 UTC (permalink / raw)
To: gitzilla; +Cc: Mark Wooding, git
In-Reply-To: <4414747B.7040700@gmail.com>
A Large Angry SCM wrote:
> Mark Wooding wrote:
>
>> Linus Torvalds <torvalds@osdl.org> wrote:
>>
>>> So in modern C, using NULL at the end of a varargs array as a pointer
>>> is perfectly sane, and the extra cast is just ugly and bowing to bad
>>> programming practices and makes no sense to anybody who never saw the
>>> horror that is K&R.
>>
>> No! You can still get bitten. You're lucky that on common platforms
>> all pointers look the same, but if you find one where `char *' (and
>> hence `void *') isn't the same as `struct foo *' then, under appropriate
>> circumstances you /will/ unless you put the casts in.
>
> Please explain how malloc() can work on such a platform. My reading of
> the '89 ANSI C spec. finds that _ALL_ (non function) pointers _are_
> cast-able to/from a void * and that NULL should be #defined as (void *).
> See 3.2.2.3 and 4.1.5 if interested.
Consider the non-hypothetical example of a word-addressed machine, which
has to have extra bits in a subword pointer like char *. The C standard
requires that void * has those bits as well, but it doesn't means that
any void * can be cast to any arbitrary pointer -- the opposite,
however, is required.
-hpa
^ permalink raw reply
* Re: [PATCH] Use explicit pointers for execl...() sentinels.
From: Jeff King @ 2006-03-13 3:31 UTC (permalink / raw)
To: git
In-Reply-To: <20060312200812.3fb04638.tihirvon@gmail.com>
On Sun, Mar 12, 2006 at 08:08:12PM +0200, Timo Hirvonen wrote:
> NULL pointer does not point to any data, it just says it's 'empty'. So
> it doesn't need to be same type pointer as specified in the function
> prototype. Pointers are just addresses, it doesn't matter from to code
> generation point of view whether it is (char *)0 or (void *)0.
Sorry, but I think you're wrong according to the C standard. Pointers of
different types do NOT have to share the same representation (e.g.,
there have been some platforms where char* and int* were different
sizes). A void pointer must be capable of representing any type of
pointer (for example, holding the largest possible type). However, if
sizeof(void *) == 8 and sizeof(char *) == 4, you have a problem with
variadic functions which are expecting to pull 4 byte off the stack.
In a non-variadic function, the compiler would do the right implicit
casting. In a variadic function, it can't.
The real question is, does git want to care about portability to such
platforms.
If you remain unconvinced, I can try to find chapter and verse of the
standard.
> sizeof(unsigned long) is sizeof(void *) in real world.
Are you saying that because it encompasses all of the platforms you've
worked on, or do you have some evidence that it is largely the case? It
certainly isn't guaranteed by the C standard.
> > Because, according to the C and POSIX specs, they're not wrong.
> They didn't think of 64-bit architectures back then, I suppose.
No, they did think of those issues; they intentionally left such sizing
up to the implementation to allow C to grow with the hardware. Mostly
you don't have to care, but as I said, typing with variadic functions is
a pain.
-Peff
^ permalink raw reply
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