On 4/10/2011 1:28 AM, Martin Pool wrote:
> ** Tags added: performance
>
Testament sha1 is currently designed to be an O(tree) validator. So we
have to load all the inventory and generate it.
The only way to have it ultimately scale is if we could only compute a
subset of the whole testament (tree based). However, the main problem is
that it becomes highly subject to how you encode the tree. And we've
tried to have Testament be decoupled from any given repository
implementation.
I see 2 options
1) Tie it to the current tree-based CHK repository implementation.
2) Create a new (semi-arbitrary) layout, but make the intermediate nodes
'cacheable' and able to be looked up based on some easy-to-compute factor.
I'm not sure what an "easy-to-compute" factor would be. Arguably it
could be the tree shape, but I don't know how you'd be able to tell that
nothing in a subtree has been modified without actually recursing into
that tree (at least with our current design).
That said, there could be some 'cheap' wins, but it would still be an
O(tree) operation.
John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 4/10/2011 1:28 AM, Martin Pool wrote:
> ** Tags added: performance
>
Testament sha1 is currently designed to be an O(tree) validator. So we
have to load all the inventory and generate it.
The only way to have it ultimately scale is if we could only compute a
subset of the whole testament (tree based). However, the main problem is
that it becomes highly subject to how you encode the tree. And we've
tried to have Testament be decoupled from any given repository
implementation.
I see 2 options
1) Tie it to the current tree-based CHK repository implementation.
2) Create a new (semi-arbitrary) layout, but make the intermediate nodes
'cacheable' and able to be looked up based on some easy-to-compute factor.
I'm not sure what an "easy-to-compute" factor would be. Arguably it
could be the tree shape, but I don't know how you'd be able to tell that
nothing in a subtree has been modified without actually recursing into
that tree (at least with our current design).
That said, there could be some 'cheap' wins, but it would still be an
O(tree) operation.
John enigmail. mozdev. org/
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://
iEYEARECAAYFAk2 hs34ACgkQJdeBCY SNAAMngACfZ3HLb fZxD5JZRXAsWz4x m8Xo cFxsVFTYD+ wUEwq5p
GYIAnRLUGUc4LZa
=5M/I
-----END PGP SIGNATURE-----