obsolete: order of magnitude speedup in _computebumpedset
Reminder: a changeset is said "bumped" if it tries to obsolete a immutable
changeset.
The previous algorithm for computing bumped changeset was:
1) Get all public changesets
2) Find all they successors
3) Search for stuff that are eligible for being "bumped"
(mutable and non obsolete)
The entry size of this algorithm is `O(len(public))` which is mostly the same as
`O(len(repo))`. Even this this approach mean fewer obsolescence marker are
traveled, this is not very scalable.
The new algorithm is:
1) For each potential bumped changesets (non obsolete mutable)
2) iterate over precursors
3) if a precursors is public. changeset is bumped
We travel more obsolescence marker, but the entry size is much smaller since
the amount of potential bumped should remains mostly stable with time `O(1)`.
On some confidential gigantic repo this move bumped computation from 15.19s to
0.46s (×33 speedup…). On "smaller" repo (mercurial, cubicweb's review) no
significant gain were seen. The additional traversal of obsolescence marker is
probably probably counter balance the advantage of it.
Other optimisation could be done in the future (eg: sharing precursors cache
for divergence detection)
DOCUMENT_ROOT="/var/www/hg"; export DOCUMENT_ROOT
GATEWAY_INTERFACE="CGI/1.1"; export GATEWAY_INTERFACE
HTTP_ACCEPT="text/xml,application/xml,application/xhtml+xml,text/html;q=0.9,text/plain;q=0.8,image/png,*/*;q=0.5"; export HTTP_ACCEPT
HTTP_ACCEPT_CHARSET="ISO-8859-1,utf-8;q=0.7,*;q=0.7"; export HTTP_ACCEPT_CHARSET
HTTP_ACCEPT_ENCODING="gzip,deflate"; export HTTP_ACCEPT_ENCODING
HTTP_ACCEPT_LANGUAGE="en-us,en;q=0.5"; export HTTP_ACCEPT_LANGUAGE
HTTP_CACHE_CONTROL="max-age=0"; export HTTP_CACHE_CONTROL
HTTP_CONNECTION="keep-alive"; export HTTP_CONNECTION
HTTP_HOST="hg.omnifarious.org"; export HTTP_HOST
HTTP_KEEP_ALIVE="300"; export HTTP_KEEP_ALIVE
HTTP_USER_AGENT="Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.8.0.4) Gecko/20060608 Ubuntu/dapper-security Firefox/1.5.0.4"; export HTTP_USER_AGENT
PATH_INFO="/"; export PATH_INFO
PATH_TRANSLATED="/var/www/hg/index.html"; export PATH_TRANSLATED
QUERY_STRING=""; export QUERY_STRING
REMOTE_ADDR="127.0.0.2"; export REMOTE_ADDR
REMOTE_PORT="44703"; export REMOTE_PORT
REQUEST_METHOD="GET"; export REQUEST_METHOD
REQUEST_URI="/test/"; export REQUEST_URI
SCRIPT_FILENAME="/home/hopper/hg_public/test.cgi"; export SCRIPT_FILENAME
SCRIPT_NAME="/test"; export SCRIPT_NAME
SCRIPT_URI="http://hg.omnifarious.org/test/"; export SCRIPT_URI
SCRIPT_URL="/test/"; export SCRIPT_URL
SERVER_ADDR="127.0.0.1"; export SERVER_ADDR
SERVER_ADMIN="eric@localhost"; export SERVER_ADMIN
SERVER_NAME="hg.omnifarious.org"; export SERVER_NAME
SERVER_PORT="80"; export SERVER_PORT
SERVER_PROTOCOL="HTTP/1.1"; export SERVER_PROTOCOL
SERVER_SIGNATURE="<address>Apache/2.0.53 (Fedora) Server at hg.omnifarious.org Port 80</address>"; export SERVER_SIGNATURE
SERVER_SOFTWARE="Apache/2.0.53 (Fedora)"; export SERVER_SOFTWARE