[BitTorrent] BT2 & hash trees - leaf size benchmarked

Elliott Mitchell ehem at m5p.com
Mon Jul 26 03:28:04 EDT 2004


>From: John Hoffman <theshadow at shambala.net>
> 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

I tried it out, and got similar numbers.

> 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.

Such a large disparity is surprising, certainly Olaf's 7% seemed low,
but a factor of 2x seems way too large. At first I thought it was the
string creation and destruction in _test(), but eliminating that gives a
flat 2x improvement, while leaving the relative scores perfectly in
place.

> 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()

Two notes here. First, "l = min(blocksize, datasize-(i+blocksize))" is
incorrect, it should be "l = min(blocksize, datasize-i)". Second changing
"g.add_block(' '*l)" to "g.add_block('\0'*l)" turns the input to zeros,
which is a more canonical test value.


Below I've included a C implementation akin to this. The data creation
and instrumentation aren't built in, it seemed viable to use external
programs for those. Pretty simple compile, but needs to be linked to
libcrypto, included with most SSL libraries (notably OpenSSL). Once
built, try `dd if=/dev/zero bs=1024k count=4096 | time ./treetest
<blocksize>`. This works pretty well on your favorite flavor of Unix.

In contrast to John's Python implementation my C implementation doesn't
see too much difference at all. On a (slow if that makes any difference)
ia32 system the time taken was remaining absolutely flat no matter the
block size. On an UltraSPARC system I was seeing a 15% difference.

The UltraSPARC result matches my expectations fairly well. The main
consumption is the handling of the blocks themselves, while the internal
nodes do make a difference. The ia32 result is surprising, but not
totally unreasonable.


So, two wildly different results. Best guess is something in Python is
killing John's implementation. I'd thought it might be the creation and
destruction of the string, but as I noted above that cuts the execution
time of all runs in half no relative changes. Might be the function call
overhead, except the disparity seems way too large for that.


>From: "Olaf van der Spek" <OvdSpek at LIACS.NL>
> So in the worst case (1 vs 16 kb) you'd be 'wasting' less than 17 s, spread
> over the entire download time?
> Suppose you're indeed downloading one gb in two hour (almost 150 kb/s), then
> CPU usage would be 0.2 % higher on average.
> Is that a huge overhead?

17 seconds of processor time. Might end up lengthening the download time
by 30 seconds (due to spreading out consumption over time). Quite a bit
worse if partial results aren't cached. File verification on startup will
be longer.

Still, I can't take issue with the above statement. The lowest level
block size won't make that big a deal in download time. I stick by my
question asking whether it is worthwhile to bother with verification at
the 4K level. (do dialup folks really ask for blocks that small?)

Now it is onto the question of intermediate levels. Allow for sending
which ones? Perhaps go for a larger fanout at that makes BT work better?

As far as adding a cookie to the hash function...  I think the approach
of running the leftover piece through the hash at each level is better
(making the distance between the root and leaves fixed, though near the
end the nodes don't fan out at all).


Now my implementation:

-----8<-----------------------------------------------------------8<-----
#include <stdio.h>
#include <stdlib.h>
#include <openssl/sha.h>

#define MAXSTACK 64
#define BUFSIZE 32768

int main(int argc, char **argv)
{
	SHA_CTX ctxs[MAXSTACK];
	char hash[SHA_DIGEST_LENGTH];
	unsigned long long blocknum, orderwork, mask;
	int shift;
	char buffer[BUFSIZE];
	char *bufwk;
	int bufcnt;
	int blocksize;
	int datacnt;
	int order;

	blocknum=1;
	blocknum<<=63;
	if(!blocknum) {
		fprintf(stderr, "ERROR: data type \"long long\" too small\n");
		return 1;
	}
	if(argc!=2) {
		fprintf(stderr, "Usage: %s <blocksize>\n", argv[0]);
		return 1;
	}
	blocksize=strtoul(argv[1], NULL, 0);
	if(blocksize&(blocksize-1)) {
		fprintf(stderr, "Illegal block size %d\n", blocksize);
		return 1;
	}
	if(blocksize>BUFSIZE) {
		fprintf(stderr, "Block size %d too big (%d maximum)\n",
blocksize, BUFSIZE);
		return 1;
	}
	shift=1;
	mask=(1<<shift)-1;

	if(blocksize) {
		blocknum=0;
		do {
			datacnt=fread(buffer, 1, BUFSIZE, stdin);
			bufwk=buffer;
			bufcnt=datacnt;
			while(bufcnt>0) {
				SHA1_Init(ctxs+0);
				SHA1_Update(ctxs+0, buffer, blocksize>bufcnt?
bufcnt:blocksize);
				SHA1_Final(hash, ctxs+0);
				bufwk+=blocksize;
				bufcnt-=blocksize;
				orderwork=blocknum;
				order=1;
				while((orderwork&mask)==mask) {
					SHA1_Update(ctxs+order, hash,
SHA_DIGEST_LENGTH);
					SHA1_Final(hash, ctxs+order);
					orderwork>>=shift;
					++order;
				}
				if(!(orderwork&mask)) SHA1_Init(ctxs+order);
				SHA1_Update(ctxs+order, hash, SHA_DIGEST_LENGTH);
				++blocknum;
			}
		} while(datacnt==BUFSIZE);
		if(blocknum>1) {
			orderwork=blocknum;
			order=1;
			while((orderwork&mask)==0) {
				orderwork>>=shift;
				++order;
			}
			orderwork>>=shift;
			++order;

			while(orderwork) {
				while((orderwork&mask)==0) {
					orderwork>>=shift;
					++order;
				}
				SHA1_Update(ctxs+order, hash, SHA_DIGEST_LENGTH);
				SHA1_Final(hash, ctxs+order);
				orderwork>>=shift;
				++order;
			}
		} else {
			if(!blocknum) {
				SHA1_Init(ctxs);
				SHA1_Final(hash, ctxs);
			}
		}
	} else {
		SHA1_Init(ctxs);
		do {
			datacnt=fread(buffer, 1, BUFSIZE, stdin);
			SHA1_Update(ctxs, buffer, datacnt);
		} while(datacnt==BUFSIZE);
		SHA1_Final(hash, ctxs);
	}

	for(datacnt=0; datacnt<SHA_DIGEST_LENGTH; ++datacnt) {
		bufcnt=(hash[datacnt]>>4)&0xF;
		if(bufcnt>=10) putchar(bufcnt-10+'A');
		else putchar(bufcnt+'0');
		bufcnt=hash[datacnt]&0xF;
		if(bufcnt>=10) putchar(bufcnt-10+'A');
		else putchar(bufcnt+'0');
	}
	putchar('\n');
	return 0;
}
-----8<-----------------------------------------------------------8<-----


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/




------------------------ Yahoo! Groups Sponsor --------------------~--> 
Yahoo! Domains - Claim yours for only $14.70
http://us.click.yahoo.com/Z1wmxD/DREIAA/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