<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>Scaling analysys of Merge — Bazaar 2.7.0 documentation</title> <link rel="stylesheet" href="_static/classic.css" type="text/css" /> <link rel="stylesheet" href="_static/pygments.css" type="text/css" /> <script type="text/javascript"> var DOCUMENTATION_OPTIONS = { URL_ROOT: './', VERSION: '2.7.0', COLLAPSE_INDEX: false, FILE_SUFFIX: '.html', HAS_SOURCE: true }; </script> <script type="text/javascript" src="_static/jquery.js"></script> <script type="text/javascript" src="_static/underscore.js"></script> <script type="text/javascript" src="_static/doctools.js"></script> <link rel="shortcut icon" href="_static/bzr.ico"/> <link rel="search" title="Search" href="search.html" /> <link rel="top" title="Bazaar 2.7.0 documentation" href="index.html" /> <link rel="stylesheet" href="_static/bzr-doc.css" type="text/css" /> </head> <body role="document"> <div class="related" role="navigation" aria-label="related navigation"> <h3>Navigation</h3> <ul> <li><a href="http://bazaar.canonical.com/"> <img src="_static/bzr icon 16.png" /> Home</a> | </li> <a href="http://doc.bazaar.canonical.com/en/">Documentation</a> | </li> <li class="nav-item nav-item-0"><a href="index.html">Developer Document Catalog (2.7.0)</a> »</li> </ul> </div> <div class="document"> <div class="documentwrapper"> <div class="bodywrapper"> <div class="body" role="main"> <div class="section" id="scaling-analysys-of-merge"> <h1>Scaling analysys of Merge<a class="headerlink" href="#scaling-analysys-of-merge" title="Permalink to this headline">¶</a></h1> <ol class="arabic simple"> <li>Fetch revisions O(a)</li> <li>Common Ancestor [O(b)] <strong>O(h)</strong></li> <li>Calculate tree merge O(c) [+ O(b) + O(d)] <strong>+ O(i)</strong></li> </ol> <blockquote> <div><ul class="simple"> <li>text merge O(e * e * f) + O(b)</li> </ul> </div></blockquote> <ol class="arabic simple" start="4"> <li>Find filesystem conflicts O(c)</li> <li>Resolve filesystem conflicts O(g)</li> <li>Apply changes O(c) + O(log(d))</li> <li>Set pending merges O(1)</li> <li>Print conflicts O(g)</li> <li>Print changes O(c)</li> </ol> <table class="docutils field-list" frame="void" rules="none"> <col class="field-name" /> <col class="field-body" /> <tbody valign="top"> <tr class="field-odd field"><th class="field-name">a:</th><td class="field-body">revisions missing from repo:</td> </tr> <tr class="field-even field"><th class="field-name">b:</th><td class="field-body">nodes in the revision graph:</td> </tr> <tr class="field-odd field"><th class="field-name">c:</th><td class="field-body">files that differ between base and other:</td> </tr> <tr class="field-even field"><th class="field-name">d:</th><td class="field-body">number of files in the tree</td> </tr> <tr class="field-odd field"><th class="field-name">e:</th><td class="field-body">number of lines in the text</td> </tr> <tr class="field-even field"><th class="field-name">f:</th><td class="field-body">number of files requiring text merge</td> </tr> <tr class="field-odd field"><th class="field-name">g:</th><td class="field-body">number of conflicts (g <= c)</td> </tr> <tr class="field-even field"><th class="field-name">h:</th><td class="field-body">humber of uncommon ancestors</td> </tr> <tr class="field-odd field"><th class="field-name">i:</th><td class="field-body">number of revisions between base and other</td> </tr> </tbody> </table> <div class="section" id="needs"> <h2>Needs<a class="headerlink" href="#needs" title="Permalink to this headline">¶</a></h2> <ul class="simple"> <li>Access to revision graph proportional to number of revisions read</li> <li>Access to changed file metadata proportional to number of changes and number of intervening revisions.</li> <li>O(1) access to fulltexts</li> </ul> </div> <div class="section" id="notes"> <h2>Notes<a class="headerlink" href="#notes" title="Permalink to this headline">¶</a></h2> <p>Multiparent deltas may offer some nice properties for performance of annotation based merging.</p> </div> </div> </div> </div> </div> <div class="sphinxsidebar" role="navigation" aria-label="main navigation"> <div class="sphinxsidebarwrapper"> <h3><a href="index.html">Table Of Contents</a></h3> <ul> <li><a class="reference internal" href="#">Scaling analysys of Merge</a><ul> <li><a class="reference internal" href="#needs">Needs</a></li> <li><a class="reference internal" href="#notes">Notes</a></li> </ul> </li> </ul> <div role="note" aria-label="source link"> <h3>This Page</h3> <ul class="this-page-menu"> <li><a href="_sources/merge-scaling.txt" rel="nofollow">Show Source</a></li> </ul> </div> <div id="searchbox" style="display: none" role="search"> <h3>Quick search</h3> <form class="search" action="search.html" method="get"> <div><input type="text" name="q" /></div> <div><input type="submit" value="Go" /></div> <input type="hidden" name="check_keywords" value="yes" /> <input type="hidden" name="area" value="default" /> </form> </div> <script type="text/javascript">$('#searchbox').show(0);</script> </div> </div> <div class="clearer"></div> </div> <div class="related" role="navigation" aria-label="related navigation"> <h3>Navigation</h3> <ul> <li><a href="http://bazaar.canonical.com/"> <img src="_static/bzr icon 16.png" /> Home</a> | </li> <a href="http://doc.bazaar.canonical.com/en/">Documentation</a> | </li> <li class="nav-item nav-item-0"><a href="index.html">Developer Document Catalog (2.7.0)</a> »</li> </ul> </div> <div class="footer" role="contentinfo"> © Copyright 2009-2011 Canonical Ltd. Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.4.9. </div> </body> </html>