> They return exactly the same thing: either null or a node or node list depending upon the method in question
...this is another thing that I'm surprised to find that people don't know. Do devs really just use these methods without ever looking at what they return or how they behave?
getElementsByClassName returns a (live) HTMLCollection, not a NodeList. querySelectorAll returns a (static) NodeList. That in itself is an obvious computational difference/potential bottleneck, because the simplest way to implement a live collection is to cache and return the same object on subsequent calls for it. And that's precisely what browsers do (getElementsByClassName('foo') === getElementsByClassName('foo')). In other words, getElementsByClassName called multiple times with the same class doesn't actually do any extra work. The real work for the browser engine, which doesn't actually happen at the point of function call, is watching any tracked class names and updating their associated HTMLCollections when an element matching that class name is added or removed from the DOM.
On the other hand, gathering the static NodeList for a querySelectorAll call requires actually iterating over the DOM to find element(s) matching the selector every time (in the naive implementation), with the trade-off of the engine not having to watch the collection internally.
As an aside, the querySelector method with an ID selector is slower but on the same order of magnitude (a difference of about a few hundred thousand ops/sec for me) as the getElementById method. So if one looks at all the data in the benchmark and not just the class ones in isolation, it becomes clear that merely parsing the selector string is not enough to drop millions/billions of operations per second down to single-digit thousands.