Perforce didn't do anything extraordinarily well, it was just dumb enough it didn't do anything particularly poorly.
Perforce had a classic file locking model where a central server was in charge of file locks and a file was read-only until it was unlocked and the number of users that could unlock a file at the same time was often as low as 1.
So even if most Perforce operations were O(n^2) or worse, they were often only n = unlocked files, not n = files in repo. git status checks the full worktree, so is n = files in (visible part of) repo.
The "file is locked by another user" problem led to doing a lot of work outside Perforce itself. Often diff and patch tools and patch queues/changeset queue tools would proliferate around Perforce repos not provided by Perforce itself, but mini-VCSes built on top of Perforce. (Which is part of why Microsoft entirely forked Perforce early on. If you are already building a VCS toolkit on top of the VCS, might as well control that, too.)
A big point about git and its support for offline work, is that it works nothing like Perforce and you mostly don't want it to. A big benefit to git's model is that we mostly aren't using git as a low-level VCS toolkit and using a diaspora of other tools on top of git. (Ironically so, given git's original intent was to be the low-level VCS toolkit and early devs expected more "porcelain" tools to be built on top of it as third-party projects.)
Perforce had a classic file locking model where a central server was in charge of file locks and a file was read-only until it was unlocked and the number of users that could unlock a file at the same time was often as low as 1.
So even if most Perforce operations were O(n^2) or worse, they were often only n = unlocked files, not n = files in repo. git status checks the full worktree, so is n = files in (visible part of) repo.
The "file is locked by another user" problem led to doing a lot of work outside Perforce itself. Often diff and patch tools and patch queues/changeset queue tools would proliferate around Perforce repos not provided by Perforce itself, but mini-VCSes built on top of Perforce. (Which is part of why Microsoft entirely forked Perforce early on. If you are already building a VCS toolkit on top of the VCS, might as well control that, too.)
A big point about git and its support for offline work, is that it works nothing like Perforce and you mostly don't want it to. A big benefit to git's model is that we mostly aren't using git as a low-level VCS toolkit and using a diaspora of other tools on top of git. (Ironically so, given git's original intent was to be the low-level VCS toolkit and early devs expected more "porcelain" tools to be built on top of it as third-party projects.)