* Re: [PATCH 1/5] revision caching documentation: man page and technical discussion
From: Sam Vilain @ 2009-08-07 3:08 UTC (permalink / raw)
To: Nick Edelen
Cc: Junio C Hamano, Johannes Schindelin, Jeff King, Shawn O. Pearce,
Andreas Ericsson, Christian Couder, git@vger.kernel.org
In-Reply-To: <op.ux8i6lq9tdk399@sirnot.private>
Nick Edelen wrote:
> Before any code is introduced the full documentation is put forth. This
> provides a man page for the porcelain, and a technical doc in technical/. The
> latter describes the API, and discusses rev-cache's design, file format and
> mechanics.
>
> Signed-off-by: Nick Edelen <sirnot@gmail.com>
>
> ---
> Documentation/rev-cache.txt | 51 +++++
> Documentation/technical/rev-cache.txt | 336 +++++++++++++++++++++++++++++++++
> 2 files changed, 387 insertions(+), 0 deletions(-)
>
A couple of minor nits here:
1. Documentation/rev-cache.txt should be
Documentation/git-rev-cache.txt, because it documents that command.
2. there are many whitespace errors:
wilber:~/src/git$ git am \[PATCH\ 1_5\]\ revision\ caching\
documentation\:\ man\ page\ and\ technical\ discussion.eml
Applying: revision caching documentation: man page and technical discussion
/home/samv/src/git/.git/rebase-apply/patch:15: trailing whitespace.
A front end for the rev-cache API is provided with the builtin utility
/home/samv/src/git/.git/rebase-apply/patch:16: trailing whitespace.
`rev-cache`. It is mainly intended for cache slice generation and
maintenance,
/home/samv/src/git/.git/rebase-apply/patch:17: trailing whitespace.
but can also walk commits within a slice. At the moment it is not
particularly
/home/samv/src/git/.git/rebase-apply/patch:34: trailing whitespace.
`\--stdin`:: Also read commit ids from stdin (seperated by newline,
`\--not`
/home/samv/src/git/.git/rebase-apply/patch:51: trailing whitespace.
`\--all`:: Include all objects in repository. Will only traverse as of
cache
warning: squelched 166 whitespace errors
warning: 171 lines add whitespace errors.
Be sure to check the patch doesn't do that...
> diff --git a/Documentation/rev-cache.txt b/Documentation/rev-cache.txt
> new file mode 100755
> index 0000000..64bd051
> --- /dev/null
> +++ b/Documentation/rev-cache.txt
> @@ -0,0 +1,51 @@
> +rev-cache porcelain
> +===================
> +
> +A front end for the rev-cache API is provided with the builtin utility
> +`rev-cache`. It is mainly intended for cache slice generation and maintenance,
> +but can also walk commits within a slice. At the moment it is not particularly
> +advanced, but is sufficient for repository administration.
>
That last sentence is a bit unnecessarily self-doubting; "It currently
provides basic functionality" would be fine.
> +
> +It's general syntax is:
> +
> +`git-rev-cache COMMAND [options] [<commit-id>...]`
> +
> +With the commands:
>
You should use the same structure and headings of this file as the other
man pages which are found under Documentation/git-*.txt
> +
> +`add`::
> + Add revisions to the cache. Reads commit ids from stdin, formatted as:
> + `END END ... \--not START START ...`
>
Really, it's reading a revision list; might be better to call it that.
Can it accept the same options as git-rev-list here or just a list of
starting points/tips? And "END" and "START" are still backwards to the
rest of git core!
> ++
> +Options:
> +
> +`\--all`:: Include all heads as ends.
> +`\--fresh`:: Exclude everything already in a cache slice.
>
If you use the paragraph layout used by other commands you can explain a
little bit more about what you mean here. By "Cache Slice" do you mean
"Revision Cache"? Does that --fresh imply that all of the revisions
which were not indexed will automatically get indexed?
> +`\--stdin`:: Also read commit ids from stdin (seperated by newline, `\--not`
> +also valid).
> +`\--legs`:: Ensure branch has no "dangling" starts (ie. is self-contained).
>
The --legs term is a little too 'cute', is there a better way to
describe this? And "starts" is not a real word in that context; if you
are using a technical term, you should define it..
> +`\--noobjects`:: Don't include non-commit objects.
> +
> +`walk`::
> + Walk a cache slice based on set of commits; formatted as add.
>
So, this works like 'rev-list' ?
"Formatted" is wrong there I think; do you mean it 'accepts the same
arguments as add' ?
> ++
> +Options:
> +
> +`\--objects`:: Include non-commit objects in traversal.
> +
>
Which was the default? --objects or --no-objects?
> +`fuse`::
> + Coagulate several cache slices into a single large slice.
>
Coagulate? You mean, the revision caches will stop being liquid and go
gluggy, like a pool of blood clotting?
How about "combine" :-) - and the option might be better called
something simple like that, too.
> ++
> +Options:
> +
> +`\--all`:: Include all objects in repository. Will only traverse as of cache
> +ends if this is not specified.
>
That sentence doesn't quite read well to me.
> +`\--noobjects`:: Don't include non-commit objects.
> +`\--ignore-size[=N]`:: Do not fuse slices of file size >= `N`. If `N` is not
> +given the cutoff size defaults to ~5MB.
> +
> +`index`::
> + Regenerate the cache index.
> +
> +
> +For an explanation of the API and its inner workings, see
> +link:technical/rev-cache.txt[technical info on rev-cache]
> diff --git a/Documentation/technical/rev-cache.txt b/Documentation/technical/rev-cache.txt
> new file mode 100755
> index 0000000..e95ec89
> --- /dev/null
> +++ b/Documentation/technical/rev-cache.txt
> @@ -0,0 +1,336 @@
> +rev-cache
> +=========
> +
> +The revision cache API ('rev-cache') provides a method for efficiently storing
> +and accessing commit branch sections. Such branch slices are defined by a
> +series of top (interesting) and bottom (uninteresting) commits. Each slice
> +contains, per commit:
> +
> +* All intra-slice topological relations, encoded into path "channels" (see
> + 'Mechanics' for full explanation).
> +* Object meta-data: type, SHA-1, size, date (for commits).
> +* Objects introduced in that commit, relative to slice (ie. only for non-start
> + commits).
> +
> +Storage data structures are not exported, in part to keep git's global scope
> +clean, but largely because they're pretty much useless outside of rev-cache.
> +
> +The API
> +-------
> +
> +The API for 'rev-cache' is quite simple. You can find the function prototypes
> +in `revision.h`.
> +
> +Data Structures
> +~~~~~~~~~~~~~~~
> +
> +The `rev_cache_info` struct holds all the options and flags for the API.
> +
> +----
> +struct rev_cache_info {
> + /* generation flags */
> + unsigned objects : 1,
> + legs : 1,
> + make_index : 1;
> +
> + /* traversal flags */
> + unsigned save_unique : 1,
> + add_to_pending : 1;
> +
> + /* fuse options */
> + unsigned int ignore_size;
> +};
> +----
> +
> +The fields:
> +
> +`objects`:: Add non-commit objects to slice.
> +`legs`:: Ensure bottoms have no childrens.
>
"children" is already plural and needs no 's'
> +`make_index`:: Integrate newly-made slice into index.
> +`save_unique`:: Load unique non-commit objects into `unique` field of each
> +`commit` object.
>
Unique how? Do you mean, that they were introduced in this slice and
not reachable from any of the bottom/end commits?
> +`add_to_pending`:: Append unique non-commit objects to the `pending` object
> +list in the passed `rev_info` instance.
>
That doesn't make much sense to me either. What does that mean? Well,
I'll read on.
> +`ignore_size`:: If non-zero, ignore slices with size greater or equal to this.
>
What will this ignoring mean?
> +Functions
> +~~~~~~~~~
> +
> +`init_rci`::
> +
> + Initiate a `rev_cache_info` struct to default options.
> +
> +`make_cache_slice`::
> +
> + Create a cache based on an a `rev_info` instance or `commit_list` s of
> + "tops" and "bottoms" (defaulting to latter if `rev_info` pointer is
> + NULL), copying the cache SHA-1 into a passed pointer if non-zero. A
> + `rev_cache_info` struct pointer can be passed to set options, while
> + passing NULL will set default options. A last parameter can
> + optionally recieve the final cache hash.
> +
> +`make_cache_index`::
> +
> + Add a slice to the cache index. Requires a file descriptor, the cache
> + hash and the file size. Note that this is normally called by
> + `make_cache_slice` under the `make_index` option.
> +
> +`get_cache_slice`::
> +
> + Given a commit SHA-1 `get_cache_slice` will search the slice index and
> + return, if found, the cache-identifying SHA-1.
> +
> +`traverse_cache_slice`::
> +
> + Traverse a specified cache slice based on:
> +
> + * `rev_cache_info` instance (optional)
> + * cache SHA-1 identifier
> + * `rev_info` instance
> + * a starting commit and commit work list
> + * date of oldest encountered interesting commit
> + * current `slop` (this and above mainly used in integration with
> + revision walker)
>
Hmm what's a 'slop' ?
> +
> ++
> +The output is sent to a FILO `commit_list` "queue", while any bottom commits
> +are passed back into the work list. If the walk is not contained within the
> +slice, commit boundaries are also inserted into "work".
> +
> +`tops_from_slices`::
> +
> + Will mark all top-commits in the specified cache slices with a given
> + flag, and add them to the rev pending list. Will include all if no
> + slices are specified.
> +
> +`coagulate_cache_slices`::
> +
> + Generate a slice based on the passed `rev_info` instance, replacing all
> + encountered slices with one (larger) slice. The `ignore_size` field in
> + `rci`, if non-zero, will dictate which cache slice sizes to ignore in
> + both traversal and replacement.
> +
> +`regenerate_index`::
> +
> + Remake cache index.
> +
> +Example Usage
> +-------------
> +
> +A few examples to demonstrate usage:
> +
> +.Creating a slice
> +----
> +/* pretend you're a porcelain for rev-cache reading from the command line */
> +struct rev_info revs;
> +struct rev_cache_info rci;
> +
> +init_revisions(&revs, 0);
> +init_rci(&rci);
> +
> +flags = 0;
> +for (i = 1; i < argc; i++) {
> + if (!strcmp(argv[i], "--not"))
> + flags ^= UNINTERESTING;
> + else if(!strcmp(argv[i], "--fresh"))
> + starts_from_slices(&revs, UNINTERESTING, 0, 0);
> + else
> + handle_revision_arg(argv[i], &revs, flags, 1);
> +}
> +
> +/* we want to explicitly set certain options */
> +rci.objects = 0;
> +
> +if (!make_cache_slice(&rci, &revs, 0, 0, cache_sha1))
> + printf("made slice! it's called %s\n", sha1_to_hex(cache_sha1));
>
Heh, normally it's acceptable to let examples in documentation not be
complete working programs :)
> +----
> +
> +.Traversing a slice
> +----
> +/* let's say you're walking the tree with a 'work' list of current heads and a
> + * FILO output list 'out' */
> +out = 0;
> +outp = &out;
> +
> +while (work) {
> + struct commit *commit = pop_commit(&work);
> + struct object *object = &commit->object;
> + unsigned char *cache_sha1;
> +
> + if (cache_sha1 = get_cache_slice(object->sha1)) {
> + /* note that this will instatiate any topo-relations
> + * as it goes */
> + if (traverse_cache_slice(&revs, cache_sha1,
> + commit, 0, 0, /* use defaults */
> + &outp, &work) < 0)
> + die("I'm overreacting to a non-fatal cache error");
> + } else {
> + struct commit_list *parents = commit->parents;
> +
> + while (parents) {
> + struct commit *p = parents->item;
> + struct object *po = &p->object;
> +
> + parents = parents->next;
> + if (po->flags & UNINTERESTING)
> + continue;
> +
> + if (object->flags & UNINTERESTING)
> + po->flags |= UNINTERESTING;
> + else if (po->flags & SEEN)
> + continue;
> +
> + if (!po->parsed)
> + parse_commit(p);
> + insert_by_date(p, &work);
> + }
> +
> + if (object->flags & (SEEN | UNINTERESTING) == 0)
> + outp = &commit_list_insert(commit, outp);
> + object->flags |= SEEN;
> + }
> +}
> +----
>
Ok, good - perhaps needs a comment or two - not much, it's already long.
> +
> +Some Internals
> +--------------
> +
> +Although you really don't need to know anything about how rev-cache actually
> +does its magic shizz, a bit of background may go a long way if you're wading
> +through the source.
>
"does its work" will do nicely..
> +
> +File Formats
> +~~~~~~~~~~~~
> +
> +A slice has a basic fixed-size header, followed by a certain number of object
> +entries. Commits are sorted in topo-order, and each commit entry is followed
> +by the objects added in that commit.
>
Starting from the top or the bottom? And it might pay to clarify which
objects are included or not; ie objects reachable from "bottom" commits
or not.
> +
> +----
> + -- +--------------------------------+
> +header | object number, etc... |
> + -- +--------------------------------+
> +commit | commit info |
> +entry | path data |
> + +--------------------------------+
> + | tree/blob info |
> + +--------------------------------+
> + | tree/blob info |
> + +--------------------------------+
> + | ... |
> + -- +--------------------------------+
> +commit | commit info |
> +entry | path data |
> + +--------------------------------+
> + | tree/blob info |
> + +--------------------------------+
> + | ... |
> + -- +--------------------------------+
> +... ...
> + +--------------------------------+
> +----
> +
> +The index is somewhat similar to pack-file indexes, containing a fanout table
> +and a list of index entries sorted by hash.
> +
> +----
> + -- +--------------------------------+
> +header | object #, cache #, etc. |
> + -- +--------------------------------+
> +cache | SHA-1 |
> +sha1s | ... |
> + -- +--------------------------------+
> +fanout | fanout[0x00] |
> +table ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> + | fanout[0xff] |
> + -- +--------------------------------+
> +index | entry SHA-1 |
> +entries | cache sha1 index |
> + +--------------------------------+
> + | |
> + ...
> + +--------------------------------+
> +----
> +
> +All the relavant structures are readily accessible in `rev-cache.c`
> +
>
Ok right so which is the on-disk container format? The index or the
slice? I'm a little confused..
> +Mechanics
> +~~~~~~~~~
> +
> +The most important part of rev-cache is its method of encoding topological
> +relations. To ensure fluid traversal and reconstruction,
Is it still fluid after coagulation? ;-)
> commits are related
> +through high-level "streams"/"channels" rather than individual
> +interconnections. Intuitively, rev-cache stores history the way gitk shows it:
> +commits strung up on lines, which interconnect at merges and branches.
> +
> +Each commit is associated to a given channel/path via a 'path id', and
> +variable-length fields govern which paths (if any) are closed or opened at that
> +object. This means that topo-data can be preserved in only a few bytes extra
> +per object entry. Other information stored per entry is the sha-1 hash, type,
> +date, size, and status in cache slice. Here is format of an object entry, both
> +on-disk and in-memory:
> +
> +----
> +struct object_entry {
> + unsigned type : 3;
> + unsigned is_end : 1;
> + unsigned is_start : 1;
> + unsigned uninteresting : 1;
> + unsigned include : 1;
> + unsigned flags : 1;
> + unsigned char sha1[20];
> +
> + unsigned merge_nr : 6;
> + unsigned split_nr : 7;
> + unsigned size_size : 3;
> +
> + uint32_t date;
> + uint16_t path;
> +
> + /* merge paths */
> + /* split paths */
> + /* size */
> +};
> +----
> +
> +An explanation of each field:
> +
> +`type`:: Object type
> +`is_end`:: The commit has some parents outside the cache slice (all if slice
> +has legs)
> +`is_start`:: The commit has no children in cache slice
> +`uninteresting`:: Run-time flag, used in traversal
> +`include`:: Run-time flag, used in traversal (initialization)
> +`flags`:: Currently unused, extra bit
> +`sha`:: Object SHA-1 hash
> +
> +`merge_nr`:: The number of paths the current channel diverges into; the current
> +path ends upon any merge.
> +`split_nr`:: The number of paths this commit ends; used on both merging and
> +branching.
> +`size_size`:: Number of bytes the object size takes up.
> +
> +merge paths:: The path IDs (16-bit) that are to be created.
> +split paths:: The path IDs (16-bit) that are to be ended.
> +size:: The size split into the minimum number of bytes.
> +
> +Each path ID refers to an index in a 'path array', which stores the current
> +status (eg. active, interestingness) of each channel.
> +
> +Due to topo-relations and boundary tracking, all of a commit's parents must be
> +encountered before the path is reallocated. This is achieved by using a
> +counter system per merge: starting at the parent number, the counter is
> +decremented as each parent is encountered (dictated by 'split paths'); at 0 the
> +path is cleared.
> +
> +Boundary tracking is necessary because non-commits are stored relative to the
> +commit in which they were introduced. If a series of commits is not included
> +in the output, the last interesting commit must be parsed manually to ensure
> +all objects are accounted for.
> +
> +To prevent list-objects from recursing into trees that we've already taken care
> +of, the flag `FACE_VALUE` is introduced. An object with this flag is not
> +explored (= "taken at face value"), significantly reducing I/O and processing
> +time.
> +
> +(NSE)
>
tl;dr but that's ok it's magic shizz.
Anyway looking nice ... see what I can say about the next patches.
sam
^ permalink raw reply
* Re: [PATCH v2] Re: mailinfo: allow individual e-mail files as input
From: Brandon Casey @ 2009-08-07 2:49 UTC (permalink / raw)
To: Nicolas Sebrecht; +Cc: gitster, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <20090807023126.GH12924@vidovic>
Nicolas Sebrecht wrote:
> The 06/08/09, Brandon Casey wrote:
>> I think it's a little strange like that though...
>>
>> {
>> sed "$1"
>> } < "$1"
>
> I'm not sure why this comment. The former
>
> sed "$1"
>
> whithout anything else is enough.
The "former", or Junio's original patch, effectively has this form:
{
sed "$1"
} < "$1"
Without reading closely enough, I thought it looked like this:
{
sed
} < "$1"
Since I didn't study the sed statement closely enough, I assumed that it was
operating on the remaining portion of the patch email that was redirected to
the block on stdin. I missed the fact that the file name was supplied to
it. My comment was that I found it strange (and maybe unintuitive, or maybe
it's just me) that "$1" was piped on stdin and it was supplied as an
argument to sed.
-brandon
^ permalink raw reply
* Re: [PATCH 0/5] Suggested for PU: revision caching system to significantly speed up packing/walking
From: Sam Vilain @ 2009-08-07 2:47 UTC (permalink / raw)
To: Johannes Schindelin
Cc: Nick Edelen, Michael J Gruber, Junio C Hamano, Jeff King,
Shawn O. Pearce, Andreas Ericsson, Christian Couder,
git@vger.kernel.org
In-Reply-To: <alpine.DEB.1.00.0908062030340.8306@pacific.mpi-cbg.de>
Johannes Schindelin wrote:
>> the short answer is that cache slices are totally independant of pack
>> files.
>>
>
> My idea with that was that you already have a SHA-1 map in the pack index,
> and if all you want to be able to accelerate the revision walker, you'd
> probably need something that adds yet another mapping, from commit to
> parents and tree, and from tree to sub-tree and blob (so you can avoid
> unpacking commit and tree objects).
>
Tying indexes together like that is not a good idea in the database
world. Especially as in this case as Nick mentions, the domain is subtly
different (ie pack vs dag). Unfortunately you just can't try to pretend
that they will always be the same; you can't force a full repack on
every ref change!
> Still, there is some redundancy between the pack index and your cache, as
> you have to write out the whole list of SHA-1s all over again. I guess it
> is time to look at the code instead of asking stupid questions.
>
"Disk is cheap" :-) It should be a welcome trade-off; perhaps it's worth
including numbers about how big the indexes are with the time
statistics. It sounds though like it should be a significant win as a
single index can be used to accelerate a wide range of rev-list
operations, and store indexes for many different questions that can be
asked.
Sam
^ permalink raw reply
* [PATCH v2] Re: mailinfo: allow individual e-mail files as input
From: Nicolas Sebrecht @ 2009-08-07 2:31 UTC (permalink / raw)
To: Brandon Casey
Cc: Nicolas Sebrecht, gitster, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <4Frzb2o8m7o4sjOhlZiN-mXQHUAsXYeImlNxZ8ANJZ5I3_S_JjSsoA@cipher.nrlssc.navy.mil>
The 06/08/09, Brandon Casey wrote:
> Whoops, I missed that "$1" argument to sed. That means the v2 followup
> patch is unnecessary since the sed is operating on a file argument
> and _not_ stdin.
Yes.
> I think it's a little strange like that though...
>
> {
> sed "$1"
> } < "$1"
I'm not sure why this comment. The former
sed "$1"
whithout anything else is enough.
--
Nicolas Sebrecht
^ permalink raw reply
* Re: [PATCH v2] Re: mailinfo: allow individual e-mail files as input
From: Brandon Casey @ 2009-08-07 2:30 UTC (permalink / raw)
To: Nicolas Sebrecht; +Cc: gitster, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <20090807015238.GF12924@vidovic>
Nicolas Sebrecht wrote:
> The 06/08/09, Brandon Casey wrote:
>
>> diff --git a/git-am.sh b/git-am.sh
>> index d64d997..49f2be4 100755
>> --- a/git-am.sh
>> +++ b/git-am.sh
>
> <...>
>
>> + {
>> + echo "$l1"
>> + echo "$l2"
>> + echo "$l3"
>> + cat
>
> UUOC, I guess.
I needed to use google to figure out that UUOC means Useless Use Of Cat,
but I think you are mistaken. Rather than trying to explain it, try this
with and without 'cat' commented out:
#!/bin/sh
{
{
echo "line one"
echo "line two"
cat
} | sed -e 's/$/Q/'
} <<-EOF
This is a line of text
Here is another line of text.
And another
EOF
Hopefully you'll see the parallels to the sequence in git-am.sh and understand
that cat was used to send the rest of the email through sed along with the first
three lines that were read explicitly. git-am.sh looks more like this:
{
read l1
...
{
echo "$l1"
...
cat
} | sed ...
} << "$1"
At least, I thought that is how it looked until I read your other email where
you pointed out that "$1" is an argument to sed.
>> + } | sed -n -e '/^$/q' -e '/^[ ]/d' -e p "$1" |
> ^^
>
> Is it still needed?
Yes. The '/^[ ]/d' portion of the sed statement deletes any lines with
leading space or tab. This avoids passing continuation fields to the
grep statement which is not designed for them, and so would fail (or
match, depending on how you look at it. We used -v with grep).
-brandon
^ permalink raw reply
* Re: [PATCH 0/7] block-sha1: improved SHA1 hashing
From: Linus Torvalds @ 2009-08-07 2:23 UTC (permalink / raw)
To: Artur Skawina; +Cc: Git Mailing List
In-Reply-To: <alpine.LFD.2.01.0908061502570.3390@localhost.localdomain>
On Thu, 6 Aug 2009, Linus Torvalds wrote:
>
>
> On Thu, 6 Aug 2009, Artur Skawina wrote:
> >
> > Does this make any difference for you? For me it's the best one so far
> > (the linusas2 number clearly shows that for me the register renaming does
> > nothing; other than that the functions should be very similar)
>
> Nope. If anything, it's bit slower, but it might be in the noise. I
> generally got 330MB/s with my "cpp renaming" on Nehalem (32-bit - the
> 64-bit numbers are ~400MB/s), but with this I got 325MB/s twice in a row,
> which matches the linusas2 numbers pretty exactly.
I actually found a P4 I have access to, except that one is a Prescott.
And I can't run it in 32-bit mode, because I only have a regular user
login, and it only has the 64-bit development environment.
But I can do the hacked-for-64bit sha1bench runs, and I tested your patch.
It's horrible.
Here's the plain "linus" baseline (ie the "Do register rotation in cpp")
thing, with the fixed "E += TEMP .." thing):
# TIME[s] SPEED[MB/s]
rfc3174 1.648 37.03
rfc3174 1.677 36.4
linus 0.4018 151.9
linusas 0.4439 137.5
linusas2 0.4381 139.3
mozilla 0.9587 63.66
mozillaas 0.9434 64.7
and here it is with your patch:
# TIME[s] SPEED[MB/s]
rfc3174 1.667 36.61
rfc3174 1.644 37.12
linus 0.4653 131.2
linusas 0.4412 138.3
linusas2 0.4388 139.1
mozilla 0.9466 64.48
mozillaas 0.9449 64.59
(ok, so the numbers aren't horribly stable, but the "plain linus" thing
consistently outperforms here - and underperforms with your patch).
However, note that since this is the 64-bit thing, there likely aren't any
spill issues, but it's simply an issue of "just how did the array[]
accesses get scheduled" etc. And since this is a Prescott (or rather
"Xeon") P4, the shifter isn't quite as horrible as yours is. _And_ this is
a different gcc version (4.0.3).
So the numbers aren't really all that comparable. It's more an example of
"optimizing for P4 is futile, because you're just playing with total
randomness". That's like a 20MB/s difference, just from moving a few ALU
ops around a bit.
And it's entirely possible that if I had gcc-4.4 on that machine, your
patch would magically do the right thing ;)
Sadly, that machine is just a ssh gateway, so there's no real development
tools on it at all - no way to get good profiles etc. So I can't really
say exactly what the problem pattern is :(
Linus
^ permalink raw reply
* Re: [PATCH v2] Re: mailinfo: allow individual e-mail files as input
From: Brandon Casey @ 2009-08-07 2:05 UTC (permalink / raw)
To: Nicolas Sebrecht; +Cc: gitster, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <20090807015628.GG12924@vidovic>
Nicolas Sebrecht wrote:
> The 07/08/09, Nicolas Sebrecht wrote:
>> The 06/08/09, Brandon Casey wrote:
>>
>>> diff --git a/git-am.sh b/git-am.sh
>>> index d64d997..49f2be4 100755
>>> --- a/git-am.sh
>>> +++ b/git-am.sh
>> <...>
>>
>>> + {
>>> + echo "$l1"
>>> + echo "$l2"
>>> + echo "$l3"
>>> + cat
>> UUOC, I guess.
>>
>>> + } | sed -n -e '/^$/q' -e '/^[ ]/d' -e p "$1" |
>> ^^
>
> Owned by the tabulation, sorry.
>
> Do we still need the "$1"?
Whoops, I missed that "$1" argument to sed. That means the v2 followup
patch is unnecessary since the sed is operating on a file argument
and _not_ stdin. I think it's a little strange like that though...
{
sed "$1"
} < "$1"
-brandon
^ permalink raw reply
* Re: [PATCH 2/3] Re: mailinfo: allow individual e-mail files as input
From: Brandon Casey @ 2009-08-07 1:59 UTC (permalink / raw)
To: Nicolas Sebrecht; +Cc: gitster, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <20090807013650.GE12924@vidovic>
Nicolas Sebrecht wrote:
> The 06/08/09, Brandon Casey wrote:
>
>> git-am.sh | 14 ++++++++++++++
>> t/t4150-am.sh | 2 +-
>> 2 files changed, 15 insertions(+), 1 deletions(-)
>>
>> diff --git a/git-am.sh b/git-am.sh
>> index d64d997..dd60f5d 100755
>> --- a/git-am.sh
>> +++ b/git-am.sh
>> @@ -191,6 +191,20 @@ check_patch_format () {
>> esac
>> ;;
>> esac
>> + if test -z "$patch_format" &&
>> + test -n "$l1" &&
>> + test -n "$l2" &&
>> + test -n "$l3"
>> + then
>> + # This begins with three non-empty lines. Is this a
>> + # piece of e-mail a-la RFC2822? Grab all the headers,
>> + # discarding the indented remainder of folded lines,
>> + # and see if it looks like that they all begin with the
>> + # header field names...
>> + sed -n -e '/^$/q' -e '/^[ ]/d' -e p "$1" |
>> + egrep -v '^[A-Za-z]+(-[A-Za-z]+)*:' >/dev/null ||
>> + patch_format=mbox
>> + fi
>> } < "$1" || clean_abort
>> }
>
> May I ask why you resurrect this "first three lines check for rfc2822"
> instead of dumbly falling back to the "mbox" patch_format? Performance?
This at least checks that the header has the correct form for an email.
The dumb fallback to mbox format would just blindly pass the patch to
mailsplit which (I think) would just dump out an improperly formatted
email. git-am would then start the process of applying the malformed
patch and fail. With this patch, we can catch the failure earlier
and hopefully provide a better complaint to the user.
-brandon
^ permalink raw reply
* [PATCH v2] Re: mailinfo: allow individual e-mail files as input
From: Nicolas Sebrecht @ 2009-08-07 1:56 UTC (permalink / raw)
To: Nicolas Sebrecht
Cc: Brandon Casey, gitster, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <20090807015238.GF12924@vidovic>
The 07/08/09, Nicolas Sebrecht wrote:
> The 06/08/09, Brandon Casey wrote:
>
> > diff --git a/git-am.sh b/git-am.sh
> > index d64d997..49f2be4 100755
> > --- a/git-am.sh
> > +++ b/git-am.sh
>
> <...>
>
> > + {
> > + echo "$l1"
> > + echo "$l2"
> > + echo "$l3"
> > + cat
>
> UUOC, I guess.
>
> > + } | sed -n -e '/^$/q' -e '/^[ ]/d' -e p "$1" |
> ^^
Owned by the tabulation, sorry.
Do we still need the "$1"?
--
Nicolas Sebrecht
^ permalink raw reply
* Re: [PATCH 0/7] block-sha1: improved SHA1 hashing
From: Linus Torvalds @ 2009-08-07 1:55 UTC (permalink / raw)
To: Artur Skawina; +Cc: Git Mailing List
In-Reply-To: <4A7B83BC.1040606@gmail.com>
On Fri, 7 Aug 2009, Artur Skawina wrote:
>
> I also see 44 extra lea instructions, 44 less adds
add and lea (as long as the lea shift is 1) should be the same on a P4
(they are not the same on some other microarchitectures and lea can have
address generation stalls etc).
Lea, of course, gives the potential for register movement at the same time
(three-address op), and that's likely the reason for lea-vs-adds.
> and changes like:
> [...]
> mov XX(%eRX),%eRX
> xor XX(%eRX),%eRX
> - and %eRX,%eRX
> + and XX(%eRX),%eRX
Yeah, different spill patterns. That's the biggest issue, I think.
In particular, on P4, with unlucky spills, you may end up with things like
ror $2,reg
mov reg,x(%esp)
.. a few instructions ..
xor x(%esp), reg
and the above is exactly when one of the worst P4 problems hit: a store,
followed a few cycles later by a load from the same address (and "a few
cycles later" can be quite a few instructions if they are the nice ones).
What can happen is that if the store data isn't ready yet (because it
comes from a long-latency op like a shift or a multiply), then you hit a
store buffer replay thing. The P4 (with its long pipeline) basically
starts the load speculatively, and if anything bad happens for the load
(L1 cache miss, TLB miss, store buffer fault, you name it), it will cause
a replay of the whole pipeline.
Which can take tens of cycles.
[ That said, it's been a long time since I did a lot of P4 worrying. So I
may mis-remember the details. But that whole store buffer forwarding had
some really nasty replay issues ]
> which could mean that gcc did a better job of register allocation
> (where "better job" might be just luck).
I suspect that's the biggest issue. Just _happening_ to get the spills so
that they don't hurt. And with unlucky scheduling, you might hit some of
the P4 replay issues every single time.
There are some P4 optimizations that are simple:
- avoid complex instructions
- don't blow the trace cache
- predictable branches
but the replay faults can really get you.
Linus
^ permalink raw reply
* [PATCH v2] Re: mailinfo: allow individual e-mail files as input
From: Nicolas Sebrecht @ 2009-08-07 1:52 UTC (permalink / raw)
To: Brandon Casey; +Cc: gitster, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <fmF7fF0TYh9QnFuUzmi-Zw9fKRhYn2-S-kCVb2e-d84D87BPqjfwrwFursOoLGkB99qKJmb_oRs@cipher.nrlssc.navy.mil>
The 06/08/09, Brandon Casey wrote:
> diff --git a/git-am.sh b/git-am.sh
> index d64d997..49f2be4 100755
> --- a/git-am.sh
> +++ b/git-am.sh
<...>
> + {
> + echo "$l1"
> + echo "$l2"
> + echo "$l3"
> + cat
UUOC, I guess.
> + } | sed -n -e '/^$/q' -e '/^[ ]/d' -e p "$1" |
^^
Is it still needed?
--
Nicolas Sebrecht
^ permalink raw reply
* [PATCH 2/3] Re: mailinfo: allow individual e-mail files as input
From: Nicolas Sebrecht @ 2009-08-07 1:36 UTC (permalink / raw)
To: Brandon Casey; +Cc: gitster, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <COrzR9ThNBy5SQ7chsXyUB30jVGIijxZQ3LI9L_y7Ab5vWcDcy_HolvjjuHTC7DHI9ntV-eR_v0@cipher.nrlssc.navy.mil>
The 06/08/09, Brandon Casey wrote:
> git-am.sh | 14 ++++++++++++++
> t/t4150-am.sh | 2 +-
> 2 files changed, 15 insertions(+), 1 deletions(-)
>
> diff --git a/git-am.sh b/git-am.sh
> index d64d997..dd60f5d 100755
> --- a/git-am.sh
> +++ b/git-am.sh
> @@ -191,6 +191,20 @@ check_patch_format () {
> esac
> ;;
> esac
> + if test -z "$patch_format" &&
> + test -n "$l1" &&
> + test -n "$l2" &&
> + test -n "$l3"
> + then
> + # This begins with three non-empty lines. Is this a
> + # piece of e-mail a-la RFC2822? Grab all the headers,
> + # discarding the indented remainder of folded lines,
> + # and see if it looks like that they all begin with the
> + # header field names...
> + sed -n -e '/^$/q' -e '/^[ ]/d' -e p "$1" |
> + egrep -v '^[A-Za-z]+(-[A-Za-z]+)*:' >/dev/null ||
> + patch_format=mbox
> + fi
> } < "$1" || clean_abort
> }
May I ask why you resurrect this "first three lines check for rfc2822"
instead of dumbly falling back to the "mbox" patch_format? Performance?
--
Nicolas Sebrecht
^ permalink raw reply
* Re: [PATCH 0/7] block-sha1: improved SHA1 hashing
From: Artur Skawina @ 2009-08-07 1:30 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <alpine.LFD.2.01.0908061709400.3390@localhost.localdomain>
Linus Torvalds wrote:
>
> On Thu, 6 Aug 2009, Linus Torvalds wrote:
>> In particular, I'm thinking about the warnign in the intel optimization
>> manual:
>>
>> The rotate by immediate and rotate by register instructions are
>> more expensive than a shift. The rotate by 1 instruction has the
>> same latency as a shift.
>>
>> so it's very possible that "rotate by 1" is much better than other
>> rotates.
>
> Hmm. Probably not. Googling more seems to indicate that rotates and shifts
> have a fixed 4-cycle latency on Northwood. I'm not seeing anything that
> indicates that a single-bit rotate/shift would be any faster.
>
> (And remember, if 4 cycles doesn't sound so bad: that's enough of a
> latency to do _16_ "simple" ALU's, since they can be double-pumped in the
> two regular ALU's).
looking at the generated code, there is a lot of ro[rl] movement, so it's
likely that contributes to the problem.
I also see 44 extra lea instructions, 44 less adds and changes like:
[...]
mov XX(%eRX),%eRX
xor XX(%eRX),%eRX
- and %eRX,%eRX
+ and XX(%eRX),%eRX
xor XX(%eRX),%eRX
- add %eRX,%eRX
- ror $0x2,%eRX
- mov %eRX,XX(%eRX)
+ lea (%eRX,%eRX,1),%eRX
mov XX(%eRX),%eRX
bswap %eRX
mov %eRX,XX(%eRX)
mov %eRX,%eRX
+ ror $0x2,%eRX
+ mov %eRX,XX(%eRX)
+ mov %eRX,%eRX
rol $0x5,%eRX
mov XX(%eRX),%eRX
- mov XX(%eRX),%eRX
[...]
which could mean that gcc did a better job of register allocation
(where "better job" might be just luck).
artur
^ permalink raw reply
* [PATCH v2] mailinfo: allow individual e-mail files as input
From: Brandon Casey @ 2009-08-07 1:27 UTC (permalink / raw)
To: gitster; +Cc: ni.s, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <COrzR9ThNBy5SQ7chsXyUB30jVGIijxZQ3LI9L_y7Ab5vWcDcy_HolvjjuHTC7DHI9ntV-eR_v0@cipher.nrlssc.navy.mil>
From: Junio C Hamano <gitster@pobox.com>
We traditionally allowed a mbox file or a directory name of a maildir (but
never an individual file inside a maildir) to be given to "git am". Even
though an individual file in a maildir (or more generally, a piece of
RFC2822 e-mail) is not a mbox file, it contains enough information to
create a commit out of it, so there is no reason to reject one. Running
mailsplit on such a file feels stupid, but it does not hurt.
This builds on top of a5a6755 (git-am foreign patch support: introduce
patch_format, 2009-05-27) that introduced mailbox format detection. The
codepath to deal with a mbox requires it to begin with "From " line and
also allows it to begin with "From: ", but a random piece of e-mail can
and often do begin with any valid RFC2822 header lines.
Instead of checking the first line, we extract all the lines up to the
first empty line, and make sure they look like e-mail headers.
This fixes the test in t4150-am.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Brandon Casey <drafnel@gmail.com>
---
Maybe the second patch should be replaced with this one. The original did
not test the first three lines for conformance to RFC2822.
-brandon
git-am.sh | 19 +++++++++++++++++++
t/t4150-am.sh | 2 +-
2 files changed, 20 insertions(+), 1 deletions(-)
diff --git a/git-am.sh b/git-am.sh
index d64d997..49f2be4 100755
--- a/git-am.sh
+++ b/git-am.sh
@@ -191,6 +191,25 @@ check_patch_format () {
esac
;;
esac
+ if test -z "$patch_format" &&
+ test -n "$l1" &&
+ test -n "$l2" &&
+ test -n "$l3"
+ then
+ # This begins with three non-empty lines. Is this a
+ # piece of e-mail a-la RFC2822? Grab all the headers,
+ # discarding the indented remainder of folded lines,
+ # and see if it looks like that they all begin with the
+ # header field names...
+ {
+ echo "$l1"
+ echo "$l2"
+ echo "$l3"
+ cat
+ } | sed -n -e '/^$/q' -e '/^[ ]/d' -e p "$1" |
+ egrep -v '^[A-Za-z]+(-[A-Za-z]+)*:' >/dev/null ||
+ patch_format=mbox
+ fi
} < "$1" || clean_abort
}
diff --git a/t/t4150-am.sh b/t/t4150-am.sh
index ad2a85f..4e8e176 100755
--- a/t/t4150-am.sh
+++ b/t/t4150-am.sh
@@ -114,7 +114,7 @@ test_expect_success 'am applies patch correctly' '
test "$(git rev-parse second^)" = "$(git rev-parse HEAD^)"
'
-test_expect_failure 'am correctly applies patch from email lacking "From" in first 3 lines' '
+test_expect_success 'am correctly applies patch from email lacking "From" in first 3 lines' '
git checkout first &&
git am patch1.eml &&
! test -d .git/rebase-apply &&
--
1.6.4
^ permalink raw reply related
* Re: [PATCH 2/3] mailinfo: allow individual e-mail files as input
From: Brandon Casey @ 2009-08-07 1:21 UTC (permalink / raw)
To: Jeff King; +Cc: gitster, ni.s, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <20090807011820.GA16472@coredump.intra.peff.net>
Jeff King wrote:
> On Thu, Aug 06, 2009 at 08:08:12PM -0500, Brandon Casey wrote:
>
>> You'll notice that I changed your grep -E to an egrep and dropped the -e.
>> I do not see any other grep which uses -e, and I seem to recall Jeff King
>> actively removing -e claiming that some greps do not recognize it. I do not
>> have a perfect memory though, so apologies to Jeff if I am mistaken.
>
> Fortunately git does have a perfect memory:
:)
^ permalink raw reply
* Re: [PATCH 2/3] mailinfo: allow individual e-mail files as input
From: Jeff King @ 2009-08-07 1:18 UTC (permalink / raw)
To: Brandon Casey; +Cc: gitster, ni.s, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <COrzR9ThNBy5SQ7chsXyUB30jVGIijxZQ3LI9L_y7Ab5vWcDcy_HolvjjuHTC7DHI9ntV-eR_v0@cipher.nrlssc.navy.mil>
On Thu, Aug 06, 2009 at 08:08:12PM -0500, Brandon Casey wrote:
> You'll notice that I changed your grep -E to an egrep and dropped the -e.
> I do not see any other grep which uses -e, and I seem to recall Jeff King
> actively removing -e claiming that some greps do not recognize it. I do not
> have a perfect memory though, so apologies to Jeff if I am mistaken.
Fortunately git does have a perfect memory:
$ git log -1 --all-match --author=peff --grep=grep
commit 759ad19e772a79a2a5ae6b7377d57eb21d29e6a0
Author: Jeff King <peff@peff.net>
Date: Wed Oct 22 15:22:53 2008 -0400
submodule: fix some non-portable grep invocations
Not all greps support "-e", but in this case we can easily
convert it to a single extended regex.
The grep in question is Solaris 8's /usr/bin/grep (which also needs
"egrep" instead of "-E", as you already did).
-Peff
^ permalink raw reply
* [PATCH 3/3] git-am: print fair error message when format detection fails
From: Brandon Casey @ 2009-08-07 1:08 UTC (permalink / raw)
To: gitster; +Cc: ni.s, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <COrzR9ThNBy5SQ7chsXyUB30jVGIijxZQ3LI9L_y7Ab5vWcDcy_HolvjjuHTC7DHI9ntV-eR_v0@cipher.nrlssc.navy.mil>
From: Nicolas Sebrecht <ni.s@laposte.net>
Avoid git ending with this message:
"Patch format is not supported."
With improved error message in the format detection failure case by
Giuseppe Bilotta.
Signed-off-by: Nicolas Sebrecht <ni.s@laposte.net>
Signed-off-by: Brandon Casey <drafnel@gmail.com>
---
git-am.sh | 6 +++++-
1 files changed, 5 insertions(+), 1 deletions(-)
diff --git a/git-am.sh b/git-am.sh
index dd60f5d..f719f6e 100755
--- a/git-am.sh
+++ b/git-am.sh
@@ -268,7 +268,11 @@ split_patches () {
msgnum=
;;
*)
- clean_abort "Patch format $patch_format is not supported."
+ if test -n "$parse_patch" ; then
+ clean_abort "Patch format $patch_format is not supported."
+ else
+ clean_abort "Patch format detection failed."
+ fi
;;
esac
}
--
1.6.4
^ permalink raw reply related
* [PATCH 2/3] mailinfo: allow individual e-mail files as input
From: Brandon Casey @ 2009-08-07 1:08 UTC (permalink / raw)
To: gitster; +Cc: ni.s, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <COrzR9ThNBy5SQ7chsXyUOUuBmX-VWMCz3MUVwvBOlIZzlIXRRMP6EMS7BRy_6uJvxt5H-FbtdY@cipher.nrlssc.navy.mil>
From: Junio C Hamano <gitster@pobox.com>
We traditionally allowed a mbox file or a directory name of a maildir (but
never an individual file inside a maildir) to be given to "git am". Even
though an individual file in a maildir (or more generally, a piece of
RFC2822 e-mail) is not a mbox file, it contains enough information to
create a commit out of it, so there is no reason to reject one. Running
mailsplit on such a file feels stupid, but it does not hurt.
This builds on top of a5a6755 (git-am foreign patch support: introduce
patch_format, 2009-05-27) that introduced mailbox format detection. The
codepath to deal with a mbox requires it to begin with "From " line and
also allows it to begin with "From: ", but a random piece of e-mail can
and often do begin with any valid RFC2822 header lines.
Instead of checking the first line, we extract all the lines up to the
first empty line, and make sure they look like e-mail headers.
This fixes the test in t4150-am.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Brandon Casey <drafnel@gmail.com>
---
Junio,
You'll notice that I changed your grep -E to an egrep and dropped the -e.
I do not see any other grep which uses -e, and I seem to recall Jeff King
actively removing -e claiming that some greps do not recognize it. I do not
have a perfect memory though, so apologies to Jeff if I am mistaken.
-brandon
git-am.sh | 14 ++++++++++++++
t/t4150-am.sh | 2 +-
2 files changed, 15 insertions(+), 1 deletions(-)
diff --git a/git-am.sh b/git-am.sh
index d64d997..dd60f5d 100755
--- a/git-am.sh
+++ b/git-am.sh
@@ -191,6 +191,20 @@ check_patch_format () {
esac
;;
esac
+ if test -z "$patch_format" &&
+ test -n "$l1" &&
+ test -n "$l2" &&
+ test -n "$l3"
+ then
+ # This begins with three non-empty lines. Is this a
+ # piece of e-mail a-la RFC2822? Grab all the headers,
+ # discarding the indented remainder of folded lines,
+ # and see if it looks like that they all begin with the
+ # header field names...
+ sed -n -e '/^$/q' -e '/^[ ]/d' -e p "$1" |
+ egrep -v '^[A-Za-z]+(-[A-Za-z]+)*:' >/dev/null ||
+ patch_format=mbox
+ fi
} < "$1" || clean_abort
}
diff --git a/t/t4150-am.sh b/t/t4150-am.sh
index ad2a85f..4e8e176 100755
--- a/t/t4150-am.sh
+++ b/t/t4150-am.sh
@@ -114,7 +114,7 @@ test_expect_success 'am applies patch correctly' '
test "$(git rev-parse second^)" = "$(git rev-parse HEAD^)"
'
-test_expect_failure 'am correctly applies patch from email lacking "From" in first 3 lines' '
+test_expect_success 'am correctly applies patch from email lacking "From" in first 3 lines' '
git checkout first &&
git am patch1.eml &&
! test -d .git/rebase-apply &&
--
1.6.4
^ permalink raw reply related
* [PATCH 1/3] t4150-am: demonstrate git-am's failure to handle some patch emails
From: Brandon Casey @ 2009-08-07 1:08 UTC (permalink / raw)
To: gitster; +Cc: ni.s, giuseppe.bilotta, git, Brandon Casey
In-Reply-To: <MEhvdM_GHnyaFj9ZU3lxKS47vmOk5BKslGm0FxkE_lg0SQT5Zx6KhA@cipher.nrlssc.navy.mil>
From: Brandon Casey <drafnel@gmail.com>
Recently git-am gained the ability to detect and apply patches from some
foreign VCS's. The detection of traditional patch emails though is somewhat
limited and will fail if a "From" field is not detected in the first three
lines of the email header. Demonstrate the failure by supplying a
perfectly valid email to git-am which it formerly could successfully apply.
Signed-off-by: Brandon Casey <drafnel@gmail.com>
---
t/t4150-am.sh | 15 +++++++++++++++
1 files changed, 15 insertions(+), 0 deletions(-)
diff --git a/t/t4150-am.sh b/t/t4150-am.sh
index a12bf84..ad2a85f 100755
--- a/t/t4150-am.sh
+++ b/t/t4150-am.sh
@@ -77,6 +77,12 @@ test_expect_success setup '
git commit -s -F msg &&
git tag second &&
git format-patch --stdout first >patch1 &&
+ {
+ echo "X-Fake-Field: Line One" &&
+ echo "X-Fake-Field: Line Two" &&
+ echo "X-Fake-Field: Line Three" &&
+ git format-patch --stdout first | sed -e "1d"
+ } > patch1.eml &&
sed -n -e "3,\$p" msg >file &&
git add file &&
test_tick &&
@@ -108,6 +114,15 @@ test_expect_success 'am applies patch correctly' '
test "$(git rev-parse second^)" = "$(git rev-parse HEAD^)"
'
+test_expect_failure 'am correctly applies patch from email lacking "From" in first 3 lines' '
+ git checkout first &&
+ git am patch1.eml &&
+ ! test -d .git/rebase-apply &&
+ test -z "$(git diff second)" &&
+ test "$(git rev-parse second)" = "$(git rev-parse HEAD)" &&
+ test "$(git rev-parse second^)" = "$(git rev-parse HEAD^)"
+'
+
GIT_AUTHOR_NAME="Another Thor"
GIT_AUTHOR_EMAIL="a.thor@example.com"
GIT_COMMITTER_NAME="Co M Miter"
--
1.6.4
^ permalink raw reply related
* Re: [PATCH 0/7] block-sha1: improved SHA1 hashing
From: Artur Skawina @ 2009-08-07 0:53 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <alpine.LFD.2.01.0908061609340.3390@localhost.localdomain>
Linus Torvalds wrote:
>
> Just out of curiosity, does anything change if you change the
>
> B = SHA_ROR(B,2)
>
> into a
>
> B = SHA_ROR(SHA_ROR(B,1),1)
>
> instead? It's very possible that it becomes _much_ worse, but I guess it's
Did try that yesterday, didn't help. Will recheck now.. yep:
before: linus 0.3554 171.7
after: linus 0.407 150
still true for the current version.
> So optimizing for P4 is often the wrong thing.
>
> Secondly, P4's are going away. You may have one, but they are getting
> rare. So optimizing for them is a losing proposition in the long run.
Sure, no argument; it's just that avoiding the P4 pitfalls is usually
not that hard and the impact on other, non-netburst, archs is low.
There are a lot of P4s out there and they're not going away soon.
(i'm still keeping most of my git trees on a P3...)
For generic C code such as this the difference for your i7 was -2% and
+70% for my P4; all the other (but one, i think) optimizations which
worked on P4 also applied to 32-bit i7. As i happen to have a p4 i can
just as well test the code on it, many improvements will likely apply
to other cpus too. That's all, i doubt anybody seriously considered
"optimizing for P4"; there is a reason intel discontinued them :)
The atom is a more important target, but only the asm versions did well
there so far.
artur
^ permalink raw reply
* Re: [PATCH] gitweb: parse_commit_text encoding fix
From: Jakub Narebski @ 2009-08-07 0:41 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Zoltán Füzesi
In-Reply-To: <7viqh43vz3.fsf@alter.siamese.dyndns.org>
On Tue, 4 Aug 2009, Junio C Hamano wrote:
> Zoltán Füzesi <zfuzesi@eaglet.hu> writes:
>
> > Call to_utf8 when parsing author and committer names, otherwise they will appear
> > with bad encoding if they written by using chop_and_escape_str.
> >
> > Signed-off-by: Zoltán Füzesi <zfuzesi@eaglet.hu>
> > ---
>
> Thanks, Zoltán.
>
> We should be able to set up a script that scrapes the output to test this
> kind of thing. We may not want to have a test pattern that matches too
> strictly for the current structure and appearance of the output
> (e.g. counting nested <div>s, presentation styles and such), but if we can
> robustly scrape off HTML tags (e.g. "elinks -dump") and check the
> remaining payload, it might be enough.
>
> Jakub what do you think? I suspect that scraping approach may turn out to
> be too fragile for tests to be worth doing, but I am just throwing out a
> thought.
First, I'd like to have existing t9500-gitweb-standalone-no-errors.sh
be about Perl errors and warning only, as it is now. Anything outside
this should IMVHO be put in separate test.
Second, for checking whether gitweb handles non US-ASCII input correctly
we don't need HTML scrapping or parsing. We can simply check if we have
correct string in output... and (after Zoltán Füzesi example) that we
don't have incorrect one. For example if we have 'xxxóxxx' in input,
then there is 'xxxóxxx' in output, and that all match againts 'xxx.xxx'
matches 'xxxóxxx'.
--
Jakub Narebski
Poland
^ permalink raw reply
* Re: [PATCH 0/5] Suggested for PU: revision caching system to significantly speed up packing/walking
From: Nick Edelen @ 2009-08-07 0:15 UTC (permalink / raw)
To: gitzilla
Cc: Shawn O. Pearce, Johannes Schindelin, Michael J Gruber,
Junio C Hamano, Jeff King, Sam Vilain, Andreas Ericsson,
Christian Couder, git@vger.kernel.org
In-Reply-To: <4A7B6A94.9020200@gmail.com>
That would work, but I sorta like the idea of caching the actual
names. I'm thinking of having a block of slice-unique, null-seperated
names at the end of each slice (ie. not in the mapping) which is
loaded into memory (it wouldn't be very big). Then each blob/tree
object would have an variable length index referencing a particular
name.
Using the actual names would give us greater flexbility, and allow
rev-cache to output proper rev-list type output (with the names after
the hashes).
On Fri, Aug 7, 2009 at 1:43 AM, A Large Angry SCM<gitzilla@gmail.com> wrote:
> Shawn O. Pearce wrote:
>>
>> A Large Angry SCM <gitzilla@gmail.com> wrote:
>>>
>>> Shawn O. Pearce wrote:
>>>>
>>>> Nick Edelen <sirnot@gmail.com> wrote:
>>>>>
>>>>> Hrmm, I just realized that it dosn't actually cache paths/names...
>>>>
>>>> You may not need the path name, but instead the hash value that
>>>> pack-objects computes from the path name.
>>>
>>> Please do NOT expose the hash values. The hash used by pack-objects is
>>> an implementation detail of the heuristics used by the _current_ object
>>> packing code. It would be a real shame to have to maintain backward
>>> compatibility with it at some future date after the packing machinery has
>>> changed.
>>
>> This is a local cache. If there was a version number in the header,
>> and the hash function changes, we could just bump the version number
>> and invalidate all of the caches.
>>
>> No sense in storing (and doing IO of) huge duplicate string values
>> for something where we really only need 32 bits, and where a
>> recompute from scratch only costs a minute.
>>
>
> That will work for me if the cache gets a version number and iff the
> pack-objects hash code gets big warning comments about the cache code
> dependency.
>
^ permalink raw reply
* Re: [PATCH 0/7] block-sha1: improved SHA1 hashing
From: Linus Torvalds @ 2009-08-07 0:13 UTC (permalink / raw)
To: Artur Skawina; +Cc: Git Mailing List
In-Reply-To: <alpine.LFD.2.01.0908061609340.3390@localhost.localdomain>
On Thu, 6 Aug 2009, Linus Torvalds wrote:
>
> In particular, I'm thinking about the warnign in the intel optimization
> manual:
>
> The rotate by immediate and rotate by register instructions are
> more expensive than a shift. The rotate by 1 instruction has the
> same latency as a shift.
>
> so it's very possible that "rotate by 1" is much better than other
> rotates.
Hmm. Probably not. Googling more seems to indicate that rotates and shifts
have a fixed 4-cycle latency on Northwood. I'm not seeing anything that
indicates that a single-bit rotate/shift would be any faster.
(And remember, if 4 cycles doesn't sound so bad: that's enough of a
latency to do _16_ "simple" ALU's, since they can be double-pumped in the
two regular ALU's).
I think long-running ALU ops that feed into a store (spill) also happen to
be the thing that makes the dreaded store-buffer replay trap nasties
happen more (load vs store scheduled badly, and then you end up spending
tens of cycles just replaying).
Linus
^ permalink raw reply
* Re: [PATCH 0/5] Suggested for PU: revision caching system to significantly speed up packing/walking
From: A Large Angry SCM @ 2009-08-06 23:43 UTC (permalink / raw)
To: Shawn O. Pearce
Cc: Nick Edelen, Johannes Schindelin, Michael J Gruber,
Junio C Hamano, Jeff King, Sam Vilain, Andreas Ericsson,
Christian Couder, git@vger.kernel.org
In-Reply-To: <20090806233739.GL1033@spearce.org>
Shawn O. Pearce wrote:
> A Large Angry SCM <gitzilla@gmail.com> wrote:
>> Shawn O. Pearce wrote:
>>> Nick Edelen <sirnot@gmail.com> wrote:
>>>> Hrmm, I just realized that it dosn't actually cache paths/names...
>>> You may not need the path name, but instead the hash value that
>>> pack-objects computes from the path name.
>> Please do NOT expose the hash values. The hash used by pack-objects is
>> an implementation detail of the heuristics used by the _current_ object
>> packing code. It would be a real shame to have to maintain backward
>> compatibility with it at some future date after the packing machinery
>> has changed.
>
> This is a local cache. If there was a version number in the header,
> and the hash function changes, we could just bump the version number
> and invalidate all of the caches.
>
> No sense in storing (and doing IO of) huge duplicate string values
> for something where we really only need 32 bits, and where a
> recompute from scratch only costs a minute.
>
That will work for me if the cache gets a version number and iff the
pack-objects hash code gets big warning comments about the cache code
dependency.
^ permalink raw reply
* Re: [PATCH 0/7] block-sha1: improved SHA1 hashing
From: Linus Torvalds @ 2009-08-06 23:42 UTC (permalink / raw)
To: Artur Skawina; +Cc: Git Mailing List
In-Reply-To: <4A7B64F1.2000309@gmail.com>
On Fri, 7 Aug 2009, Artur Skawina wrote:
>
> Actually that's even more of a reason to make sure the code doesn't suck :)
> The difference on less perverse cpus will usually be small, but on P4 it
> can be huge.
No. First off, the things you have to do on P4 are just insane. See the
email I just sent out asking you to test whether two 1-bit rotates might
be faster than 1 2-bit rotate.
So optimizing for P4 is often the wrong thing.
Secondly, P4's are going away. You may have one, but they are getting
rare. So optimizing for them is a losing proposition in the long run.
> A few years back I found my old ip checksum microbenchmark, and when I ran
> it on a P4 (prescott iirc) i didn't believe my eyes. The straightforward
> 32-bit C implementation was running circles around the in-kernel one...
> And a few tweaks to the assembler version got me another ~100% speedup.[1]
Yeah, not very surprising. The P4 is very good at the simplest possible
kind of code that does _nothing_ fancy.
But then it completely chokes on some code. I mean _totally_. It slows
down by a huge amount if there is anything but the most trivial kinds of
instructions. And by "trivial", I mean _really_ trivial. Shifts (as in
SHA1), but iirc also things like "adc" (add with carry) etc.
So it's not hard to write code that works well on other uarchs, and then
totally blow up on P4. I think it doesn't rename the flags at all, so any
flag dependency (carry being the most common one) will stall things
horrible.
There's also a very subtle store forwarding failure thing (and a lot of
other events) that causes a nasty micro-architectural replay trap, and
again you go from "running like a bat out of hell" to "slower than a i486
at a tenth the frequency".
Really. It's disgusting. Perfectly fine code can run really slowly on the
P4 just because it hits some random internal micro-architectural flaw. And
there's a _lot_ of those "glass jaw" issues.
The best way to avoid them is to use _only_ simple ALU instructions (add,
sub, and/or/not), and to be _very_ careful with loads and stores.
Linus
^ 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