> I read that hg uses some sort of a linear-append history format, meaning that going back to past versions is O(distance) in time. Is that false?

This is pretty much completely false. Mercurial stores repository data (except for the parts that relate to the current working tree) in revlog format [1], which is specifically designed to allow retrieval of arbitary revisions in time proportional to the file size (modulo what seek times spinning platter disks may impose for uncached sectors). The revlog format is designed to be append-only, but that actually is done to keep things fast by enabling random access based on an index; it does not lead to O(history size) operations.

> I don't think hg is more scalable than git.

Git actually has made a number of conscious design decisions that limit its scalability that other versions haven't made. To understand that this is largely intentional and not likely to go away in any meaningful way anytime soon, consider this post [2] by Linus Torvalds on the Git mailing list in 2007 regarding the "git blame" problem. There is a surprising willingness there to sacrifice usability and scalability on the altar of Git's super-simple repository format.

Git's storage format is essentially a very simple transactional key-value store. While that has the benefit of allowing for a simple and robust implementation, it also makes certain operations more expensive than they need be (such as "git blame"). Some things Git can't even do, because it lacks the necessary metadata (such as avoiding spurious conflicts from first cherry-picking from a branch and later merging with the same branch). Others inherently require O(history length) or O(repository size) operations.

Git was designed by people who considered a repository with a couple of hundred MB a big project; Git really starts breaking down once you hit the 1GB barrier. Checkout the gcc repository (about 1.4GB), for example, then do "git gc", and take a coffee break, because it'll take a couple of minutes.

Somewhat famously, Facebook documented [3] some of their troubles with making Git scale.

Git, unlike Bzr or Mercurial, does not have a pluggable storage layer that can be used to easily ameliorate these shortcomings. Bzr [4], as an extreme, can cheerfully operate on a remote repository in the exact same way as a local one, because it treats local file storage vs. ssh vs. http(s) vs. sftp etc. just as different implementations of the storage layer. Facebook extended Mercurial [5] to accomplish largely the same goal.

Note that the above does not mean "Git sucks". For the most part, Git is a fine version control system, but where scalability is concerned, I'd pick a number of other VCSs first (and which is, frankly, why a lot of shops still use SVN over either Git or Mercurial; SVN may be more cumbersome to use, but it is a known quantity when it comes to handling large repositories). Git in particular is too much written like the typical C program, with a lot of concern for keeping constants low, but often with little concern for asymptotic worst-case complexity or extensibility.

> Yet for me and many users, this means we cannot go to any coworker's terminal and use those features, many of us can no longer live without.

This seems to be a workplace policy issue, not a technical concern. You can have these extensions preconfigured in a central place as part of your Mercurial installation if that's desirable.

[1] http://mercurial.selenic.com/wiki/Revlog (note that the specific format did change in v0.9, but the principles remain the same).

[2] http://marc.info/?l=git&m=116991865311836

[3] https://news.ycombinator.com/item?id=3548824

[4] Yes, I know that Bzr is not really being maintained actively by Canonical anymore, which is a shame, because in many respects, its design is far superior to either Git or Mercurial. Still, it's one of the reasons why quite a few people stick to it despite the lack of maintenance, because it bridges the gap between a fully distributed and a fully centralized VCS.

[5] https://code.facebook.com/posts/218678814984400/scaling-merc...