From: Chuck Lever <cel@citi.umich.edu>
To: Daniel Barkalow <barkalow@iabervon.org>
Cc: Linus Torvalds <torvalds@osdl.org>, git@vger.kernel.org
Subject: Re: [PATCH 21/22] teach the merge algorithm about cache iterators
Date: Thu, 15 Sep 2005 10:01:16 -0400 [thread overview]
Message-ID: <43297EAC.6020205@citi.umich.edu> (raw)
In-Reply-To: <Pine.LNX.4.63.0509141901020.23242@iabervon.org>
[-- Attachment #1: Type: text/plain, Size: 852 bytes --]
Daniel Barkalow wrote:
> On Wed, 14 Sep 2005, Linus Torvalds wrote:
>
>
>>On Wed, 14 Sep 2005, Chuck Lever wrote:
>>
>>>oh, i see. the hash table won't help cache_find_name find an insertion
>>>point quickly if the name isn't already in the cache.
>>
>>Note that almost all insertion tends to happen linearly.
>>
>>In particular, read-tree always inserts things in order.
>
> read-tree (with Chuck's latest work) should actually only append entries
> to an initially-empty list, which is even easier. Dunno about the other
> stuff, but I'd guess inserting into a cursor would handle a lot of it.
i'm implementing the splay tree now.
part of the insertion process is to splay the insertion point up to the
root of the tree. if what you and linus says is true, then the search
for the next insertion point will be very fast most of the time.
[-- Attachment #2: cel.vcf --]
[-- Type: text/x-vcard, Size: 439 bytes --]
begin:vcard
fn:Chuck Lever
n:Lever;Charles
org:Network Appliance, Incorporated;Linux NFS Client Development
adr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA
email;internet:cel@citi.umich.edu
title:Member of Technical Staff
tel;work:+1 734 763-4415
tel;fax:+1 734 763 4434
tel;home:+1 734 668-1089
x-mozilla-html:FALSE
url:http://www.monkey.org/~cel/
version:2.1
end:vcard
next prev parent reply other threads:[~2005-09-15 14:01 UTC|newest]
Thread overview: 49+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-09-12 14:55 [PATCH 00/22] cache cursors: an introduction Chuck Lever
2005-09-12 14:55 ` [PATCH 01/22] introduce facility to walk through the active cache Chuck Lever
2005-09-12 14:55 ` [PATCH 02/22] use cache iterator in checkout-index.c Chuck Lever
2005-09-12 14:55 ` [PATCH 03/22] teach diff.c about cache iterators Chuck Lever
2005-09-12 14:55 ` [PATCH 04/22] teach diff-index.c " Chuck Lever
2005-09-12 14:55 ` [PATCH 05/22] teach diff-files.c " Chuck Lever
2005-09-12 14:55 ` [PATCH 06/22] teach diff-stages.c " Chuck Lever
2005-09-12 14:55 ` [PATCH 07/22] teach fsck-objects.c to use " Chuck Lever
2005-09-12 14:56 ` [PATCH 08/22] teach ls-files.c " Chuck Lever
2005-09-12 14:56 ` [PATCH 09/22] teach read-tree.c " Chuck Lever
2005-09-12 14:56 ` [PATCH 10/22] teach update-index.c about cache cursors Chuck Lever
2005-09-12 14:56 ` [PATCH 11/22] teach write-tree.c to use cache iterators Chuck Lever
2005-09-12 14:56 ` [PATCH 12/22] simplify write_cache() calling sequence Chuck Lever
2005-09-12 14:56 ` [PATCH 13/22] move purge_cache() to read-cache.c Chuck Lever
2005-09-12 14:56 ` [PATCH 14/22] move read_cache_unmerged into read-cache.c Chuck Lever
2005-09-12 14:56 ` [PATCH 15/22] replace cache_name_pos Chuck Lever
2005-09-12 14:56 ` [PATCH 16/22] teach apply.c to use cache_find_name() Chuck Lever
2005-09-12 14:56 ` [PATCH 17/22] teach checkout-index.c " Chuck Lever
2005-09-12 14:56 ` [PATCH 18/22] teach diff.c " Chuck Lever
2005-09-12 14:56 ` [PATCH 19/22] teach ls-files.c " Chuck Lever
2005-09-12 14:56 ` [PATCH 20/22] teach merge-index.c " Chuck Lever
2005-09-12 14:56 ` [PATCH 21/22] teach the merge algorithm about cache iterators Chuck Lever
2005-09-12 20:43 ` Daniel Barkalow
2005-09-13 0:02 ` Chuck Lever
2005-09-14 15:36 ` Chuck Lever
2005-09-14 16:41 ` Daniel Barkalow
2005-09-14 17:50 ` Junio C Hamano
2005-09-14 19:49 ` Chuck Lever
2005-09-14 20:40 ` Daniel Barkalow
2005-09-14 22:28 ` Chuck Lever
2005-09-14 22:50 ` Linus Torvalds
2005-09-14 23:23 ` Daniel Barkalow
2005-09-15 14:01 ` Chuck Lever [this message]
2005-09-12 14:56 ` [PATCH 22/22] teach read-cache.c to use cache_find_name() Chuck Lever
2005-09-12 15:38 ` [PATCH 00/22] cache cursors: an introduction A Large Angry SCM
2005-09-12 16:37 ` Chuck Lever
2005-09-12 20:26 ` Daniel Barkalow
2005-09-12 20:47 ` Junio C Hamano
2005-09-13 19:06 ` Tim Ottinger
2005-09-13 19:46 ` Junio C Hamano
2005-09-13 20:06 ` Tim Ottinger
2005-09-14 8:28 ` Catalin Marinas
2005-09-14 14:49 ` Chuck Lever
2005-09-12 19:53 ` Junio C Hamano
2005-09-12 20:22 ` Daniel Barkalow
2005-09-12 20:30 ` Junio C Hamano
2005-09-12 23:59 ` Chuck Lever
2005-09-13 0:14 ` Junio C Hamano
2005-09-13 0:17 ` Linus Torvalds
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=43297EAC.6020205@citi.umich.edu \
--to=cel@citi.umich.edu \
--cc=barkalow@iabervon.org \
--cc=git@vger.kernel.org \
--cc=torvalds@osdl.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).