[BitTorrent] Performance (was Merkle, URLs, etc)
ashwood at msn.com
Fri Mar 4 19:05:50 EST 2005
----- Original Message -----
From: "Justin Cormack" <justin at street-vision.com>
Subject: [BitTorrent] Performance (was Merkle, URLs, etc)
> I thought that SHA384 might be an improvement but it
> seems to run at the same speed as SHA512 from the benchmarks I can find
> (though it saves some space).
SHA-384 is simply SHA-512 where you leave off bits of the output, so there
is no speed gain.
> Overall I would say that SHA256 is really not
> a good choice and it is best to stick with SHA1 until 64 bit machines are
> more common (rather soon it seems) and then move to SHA512.
That seems a reasonable approach, for BitTorrent purposes SHA-1 should be
usable for at least another year without any critical attack vectors opening
up, mostly because BitTorrent doesn't make a good attack target.
> In terms of hashing the internal nodes, I think the main problem is not
> the growing size, but that hashing speeds are much lower for small blocks,
> so nodes need lots of children: with openssl sha1, 3 children hash at
> half the rate of 12 children.
Agreed, making the tree flatter saves a lot of time in all stages.
>> I should say that it takes a huge amount of time build the tree
>> from a file, as I type I'm 29 minutes into processing a 180 MB file at
>> pieces ~ 95% done, and it occupies huge amounts of RAM, the test will
>> about 4 times the storage space, but has 2 copies of the original file
>> with the tree in memory at one point.
> Thats really slow. Is it swapping thats causing slowdown or other things?
> Sounds like getting the data structures right is going to be really
> with this. Clearly you dont need 2 (or any) copies of the file though and
> thats really going to hurt you. What language are you programming in?
The biggest problem didn't have to do with language, it was some idiot named
Joe decided that it wouldn't be worth programming the planned 256-ary tree
for this version and instead went with linear searching. With the search for
duplicates during insert, it slowed to a crawl. The retrieval was actually
quite good taking about a minute to retrieve and verify once the tree was
constructed, so on that front it was on par with a straight SHA-256
implementation. As to why I had 2 copies plus tree: first I load the file
(copy 1) then construct the tree, retreive the file from the tree (copy 2),
verify the file byte by byte against the original, destroy the copy (copy 2
destroy), retrieve the entire tree, save the tree to disk, destroy the tree
(and data pool), build the tree from the tree file, retrieve the original
data file (copy 2 again), verify the retrieved copy is byte for byte
correct. To do this it was rather inevitable to have 2 copies plus the tree
in memory, swapping wasn't the problem here I never exceeded physical
memory. For testing the implemenatation I decided to take this route because
I had certainty, for real implementations, 1 file copy, plus tree maximum.
The lesson to be learned is that whenever possible use n-ary search
algorithms and avoid linear. A good indicator of the difference this makes
is what happened when I ran the same file through at 4KB and 1MB block
sizes, the 4KB took about 45 minutes of CPU time to run through, the 1MB too
43 seconds. The search algorithm makes an enormous difference.
Yahoo! Groups Links
<*> To visit your group on the web, go to:
<*> To unsubscribe from this group, send an email to:
BitTorrent-unsubscribe at yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
More information about the BitTorrent