[BitTorrent] BT2 & hash trees - leaf size benchmarked

John Hoffman theshadow at shambala.net
Fri Jul 23 23:20:49 EDT 2004


Someone inquired (MUCH more politely than Olaf) about the algorithm I 
used to generate the hashes, and pointed out that CPU caching behavior 
might've been the cause of the benchmark differences I'd noted; I 
agreed, and decided to rewrite the benchmark.

The attached benchmark uses a stack-based system for storing hashes and 
only retains data as needed to find the root hash; as such, it is not 
appropriate for the actual client, but would be useful for a 
"makemetafile" function and also gives some idea how much overhead might 
be needed for generating hashes for chunks.

Running stack_based_sha_tree.test() returned (for me, YMMV):
{ leaf_node_size seconds_to_hash_1GB }
 >>> Script1.test()
512 48.3537885402
1024 30.8940586024
2048 21.9012997462
4096 17.3593610361
8192 15.0708657106
16384 13.928948791
32768 13.4034861973

Note that using a 1K leaf size uses more than 2X the CPU as using a 16K 
leaf size.  Given this, I'd have to recommend a leaf size of 4K at the 
smallest, and larger would be better.

  ----------

from sha import sha
from time import clock

class RootHashGen:
    def __init__(self):
        self.stack = []

    def add_block(self, block):
        hash = sha(block).digest()
        level = 0
        if self.stack:
            bottomhash, bottomlevel = self.stack[-1]
            while level == bottomlevel:
                hash = sha(bottomhash+hash).digest()
                level += 1
                self.stack.pop()
                if not self.stack:
                    break
                bottomhash, bottomlevel = self.stack[-1]
        self.stack.append((hash,level))

    def get_root(self):
        hash, level = self.stack.pop()
        while self.stack:
            bottomhash, bottomlevel = self.stack.pop()
            hash = sha(bottomhash+hash).digest()
        return hash
            

def _test(datasize, blocksize):
    g = RootHashGen()
    for i in xrange(0, datasize, blocksize):
        l = min(blocksize, datasize-(i+blocksize))
        g.add_block(' '*l)
    return g.get_root()

def test():
    for i in [512,1024,2048,4096,8192,16384,32768]:
        t = clock()
#        for j in xrange(100):
#            _test(10*1024*1024,i)
        _test(1024*1024*1024,i)
        print i,clock()-t

[Non-text portions of this message have been removed]



------------------------ Yahoo! Groups Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!
http://us.click.yahoo.com/L5YrjA/eSIIAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
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:
    BitTorrent-unsubscribe at yahoogroups.com

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



More information about the BitTorrent mailing list