Re: Performance (was Merkle, URLs, etc)

----- Original Message ----- 
From: "Justin Cormack" <[email protected]>
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 
>> 4kb
>> pieces ~ 95% done, and it occupies huge amounts of RAM, the test will 
>> occupy
>> about 4 times the storage space, but has 2 copies of the original file 
>> along
>> 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 
> important
> 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.
                Joe 



 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/