Firefox 50.0 [LWN.net]

Mozilla has released Firefox 50.0. This version features improved performance for SDK extensions or extensions using the SDK module loader, added download protection for a large number of executable file types, added option to Find in page that allows users to limit search to whole words only, and more. See the release notes for details.

to post comments

Firefox 50.0

Posted Nov 15, 2016 21:44 UTC (Tue) by mark625 (guest, #13741) [Link] (26 responses)

Great Gnu! Mozilla uses a linear comparison of almost 300 file extension strings (ignoring commented out lines) to determine if each downloaded file is an executable file type?! I'm no expert, but wouldn't that be a good place to use a hash table, which would be built the first time the function was called?

return
// Extracted from the "File Type Policies" Chrome extension
//StringEndsWith(fileName, NS_LITERAL_STRING(".001")) ||
//StringEndsWith(fileName, NS_LITERAL_STRING(".7z")) ||
//StringEndsWith(fileName, NS_LITERAL_STRING(".ace")) ||
StringEndsWith(fileName, NS_LITERAL_STRING(".action")) || // Mac script
....
StringEndsWith(fileName, NS_LITERAL_STRING(".zipx")); // WinZip

Also, this code finds the file extension of the filename on each call, instead of once at the top.

I suppose the excuse is that it is not performance critical. But sheesh. How bout this instead:

int is_executable(const char *fileName)
{
static hash_table *tbl = 0;
if (!hash_table) { // build it from those string literals or, I don't know, a resource file?
...
}
assert(hash_table);
return string_in_table(tbl, get_extension(fileName));
}

(Sorry for ye olde C syntax, my roots are showing.)

They use the exact same approach in an adjacent method, although it is only 20 lines long. So this is probably a standard Mozilla technique. Ugh.

Firefox 50.0

Posted Nov 15, 2016 21:59 UTC (Tue) by mark625 (guest, #13741) [Link] (15 responses)

of course it would be:

if (!tbl) { // build it
...
}
assert(tbl);
etc...

Integrated brain compiler finally saw that error. :)

Also, I don't know about NS_LITERAL_STRING(), I assume it's a macro with no runtime overhead. But maybe I assume too much. If it generates any code, that would make things even worse.

Firefox 50.0

Posted Nov 15, 2016 23:02 UTC (Tue) by excors (subscriber, #95769) [Link] (14 responses)

https://dxr.mozilla.org/mozilla-central/source/xpcom/stri... says NS_LITERAL_STRING constructs an nsLiteralString, whose definition I think is nsTLiteralString_CharT (renamed to nsLiteralString via macros in another file) which inherits from nsString, which is defined as nsTString_CharT which inherits from nsAString, which is defined as nsTSubstring_CharT, which, I dunno, I think it copies the string but I got bored trying to follow it.

But as you said, it's not performance critical. Optimisations increase the risk of bugs (e.g. your suggested code isn't thread-safe), so should only be used when they're worth the risk.

But apparently the code generated by GCC for that function is huge, which does hurt. https://hg.mozilla.org/mozilla-central/rev/4335472b7aa7 cleans it up a bit (and also makes it use nsDependentString, which I guess might avoid the copying).

Firefox 50.0

Posted Nov 16, 2016 8:20 UTC (Wed) by diegor (subscriber, #1967) [Link] (13 responses)

What about something like this:

char *exec_extensions=".exe.zip.zipx.etc.etc.";
char *ext = extractExtension(filename); // return a pointer to the char following the last dot, null if no extension

return (!ext) || (!strstr(extensions, "."+ext+".");

(ok i'm not proficient in c++, so i'm sure this code don't even compile...)

Yes, it's a bit more complex, and prone to error, but only the first time. Than adding and deleting extension is easy and clueless.

Firefox 50.0

Posted Nov 16, 2016 8:29 UTC (Wed) by zdzichu (subscriber, #17118) [Link] (12 responses)

Seriously? Checking the extension of downloaded file is so infrequent operation that time wasted on discussing implementation will never be reclaimed. This is not a performance critical part and never will be. Readability of the source code is paramount in this case.

Firefox 50.0

Posted Nov 16, 2016 13:39 UTC (Wed) by epa (subscriber, #39769) [Link]

It is an illustrative example of the maxim that if you like sausages, don't watch them being made.

Firefox 50.0

Posted Nov 16, 2016 15:04 UTC (Wed) by mark625 (guest, #13741) [Link] (9 responses)

My concern was not that this particular function would cause a performance problem itself. My concern was that this was such a horrible design pattern, and that it may be replicated elsewhere in the code base. I noted that the same technique was used in an adjacent function, though it was only 20 hard-coded sequential string comparisons instead of 300.

Even the patch that was submitted to clean this up still does a sequential search of the entire table, and still extracts the file extension for each comparison. If that kind of unnecessary CPU churn is replicated throughout the code base, it will certainly be reflected in the end result. How many times have we heard how bloated and slow Firefox has become over the years?

Details matter, and little inefficiencies here and there add up when you're talking about tens of thousands of lines of code.

Firefox 50.0

Posted Nov 16, 2016 15:29 UTC (Wed) by raven667 (subscriber, #5198) [Link] (8 responses)

> Details matter, and little inefficiencies here and there add up when you're talking about tens of thousands of lines of code.

Efficiency gains should be targeted based on real world profiling and not based on review of code that "looks slow" as you will waste a ton of time lost in the details, chasing down non-existent performance problems, sometimes making things worse if you fight the compiler, and missing the big issues which are usually more fundamental to the design and data structure usage or locking in the hottest paths of the application.

Firefox 50.0

Posted Nov 16, 2016 15:51 UTC (Wed) by pizza (subscriber, #46) [Link] (2 responses)

> Efficiency gains should be targeted based on real world profiling and not based on review of code that "looks slow"

I cannot emphasize the importance of this. Not only do the real bottlenecks turn out to be in non-obvious places, but the "obvious" stuff turns out to be pretty minor in the end.

(Granted, in this particular case the benefit was on the code readibility/maintainability front)

Firefox 50.0

Posted Nov 16, 2016 18:51 UTC (Wed) by excors (subscriber, #95769) [Link] (1 responses)

I don't want to disagree with the exhortation to use a profiler, because that's almost always the right thing to do, but might quibble a bit:

Focusing on bottlenecks is definitely much better than relying on hunches, but you may still end up in a situation where the profiler shows no individual function is using >1% of the CPU time yet your program is a quarter of the speed you need it to be.

Sometimes that might be because of a slightly inefficient design pattern that is pervasive throughout your code (e.g. maybe you're passing strings by value everywhere so it does a little memory allocation and copying on every function call, or whatever), and it never showed up in the profiler because it was a tiny cost in each of ten thousand places, but in total it adds up to a huge cost, and by the time you realise the problem it's really hard to fix. (Maybe you want to change all your strings to pass-by-reference instead, but you never previously had to care about the lifetimes of strings and you're going to end up with dangling references unless you're extremely careful when fixing every single one of those ten thousand occurrences.)

Sometimes it might be because you wrote all your code in Python, thinking you could optimise it later by profiling it and moving the hot functions to C, but after doing that you find most of your processing time is spread evenly through your remaining hundred thousand lines of Python, and the only way to fix it is to rewrite pretty much the entire thing in a faster language.

I guess the most serious performance problems are usually due to poor architecture, which is even harder to solve.

Profiling tools only help after you've written the code and run it under a realistic workload, and by then it might be too late to fix it.

If you anticipate those problems right at the start of the project, you can easily use a better design pattern or a more appropriate language etc and avoid the problem entirely. Or you can use more complicated abstractions in your code, so that it's easier to rewrite or rearchitect parts of it in the future without impacting the entire codebase. On the other hand, you might guess wrong and waste a large amount of effort solving a non-problem, and the abstractions might cost more than they save. I'm not sure there's any good way to handle that other than having experience of writing similar programs before, so you can better estimate the performance risks and see where it's worth spending a bit more effort at the start to reduce those risks.

I expect a program like Firefox is at the point where all the obvious bottlenecks have been squashed, and most of the non-obvious ones, so the problems that remain are the architectural ones and the ones that can only be solved by learning from experience and writing a new browser from scratch. (Is Servo doing a good job at learning from Firefox?)

Firefox 50.0

Posted Nov 16, 2016 20:52 UTC (Wed) by roc (subscriber, #30627) [Link]

> Is Servo doing a good job at learning from Firefox?

As former Mozilla "Distinguished Engineer" who talked to the Servo devs quite a lot over the years, trying to help them learn from Firefox --- I think so.

Firefox 50.0

Posted Nov 16, 2016 16:28 UTC (Wed) by mark625 (guest, #13741) [Link] (4 responses)

So inelegant code and obvious inefficiencies are fine until they are bad enough to show up in a profiling run? Huh. Someone at Mozilla must disagree with you, since they already took a stab at cleaning this up.

I certainly agree that profiling is a critical tool to use when performance problems do arise.

Anyway, thanks for the replies.
Cheers!

Firefox 50.0

Posted Nov 16, 2016 19:07 UTC (Wed) by raven667 (subscriber, #5198) [Link] (1 responses)

> So inelegant code and obvious inefficiencies are fine until they are bad enough to show up in a profiling run?

Yes. I'm going to reiterate what pizza said upthread, the "obvious" is usually irrelevant and the real profiling problems are often a surprise.

Firefox 50.0

Posted Nov 17, 2016 23:10 UTC (Thu) by moltonel (subscriber, #45207) [Link]

Sure, the performance of this code really doesn't matter (even it took 0.1s, nobody would notice because it only happens once per download, which are comparatively rare and slow operations).

But the fact that "obviously inelegant and slow" code was submited understandably raises some eyebrows. Why didn't the v1 of the patch construct a hash table, or some similar "obvious and easy" implementation which would hardly have taken more time to write ? Apparently the commiter would say it wasn't worth the effort, while others say the effort was minimal. It looks minimal to me, so I wonder how many other places in the code that minimal effort was not taken. How many such slight ineficiencies survive in the code because they are too spread out to show up in profiling and because the "it's ok to commit obviously inelegant and slow code, we'll profile later" mentality prevails ?

Performance-tuning an initial implementation is a balancing act. You don't want to go all-out because it's likely going to be wasted effort, but you do want to make things reasonably performant as a matter of course because you might never get a second look at that code and because you miss out on training yourself to see obvious easy optimisations. The ideal middle-ground is subjective. And in this case, a few people think the bar was set too low. Now less LWN comments, more merge requests :p

Firefox 50.0

Posted Nov 16, 2016 20:50 UTC (Wed) by roc (subscriber, #30627) [Link] (1 responses)

Cleaning up code by making it simpler is almost always a good idea. (And simplicity is not just a function of the number of lines of code. 300 lines of string comparisons is very simple.)

Optimizing code to make it faster is usually the opposite of that.

You seem to be conflating the two.

Firefox 50.0

Posted Nov 16, 2016 21:42 UTC (Wed) by nybble41 (subscriber, #55106) [Link]

> Cleaning up code by making it simpler is almost always a good idea.

DRY is also almost always a good idea, and 300 lines of the form "extract the extension, then compare it against this string" is an awful lot of repetition. 300x the operations is 300x the complexity; that adds up even when the individual operations are trivial. I agree that performance is a non-issue in this instance, but I would still recommend using a data structure of some sort so that the code can be written with a single call to extract the extension and a single comparison (in a loop if necessary). An array would be fine, though in most high-level languages a membership test against a built-in hash-map or hash-set type would be even simpler to write and maintain:

isExecutable :: FilePath -> Bool
isExecutable = maybe False (`HashSet.member` execExtensions) . fileExtension

execExtensions :: HashSet.Set FilePath
execExtensions = HashSet.fromList [ "exe", "bat", "cmd", "sh", ... ]

(In Haskell this is perfectly thread-safe, even though the set is constructed on the first access. In most other languages you would need to worry about when the set is initialized.)

Firefox 50.0

Posted Nov 16, 2016 15:18 UTC (Wed) by raven667 (subscriber, #5198) [Link]

Thanks for pointing this out, I also wanted to mention that according to the notes the file list was extracted from another script, so converting it one line of code per list entry is good for the continued maintenance of the list, you can easily regenerate, diff and comment on it read-ably.

Firefox 50.0

Posted Nov 16, 2016 4:00 UTC (Wed) by josh (subscriber, #17465) [Link] (9 responses)

> wouldn't that be a good place to use a hash table, which would be built the first time the function was called?

It'd actually be a good place for a perfect hash table, built at compile time.

Firefox 50.0

Posted Nov 16, 2016 16:41 UTC (Wed) by mark625 (guest, #13741) [Link] (5 responses)

So are there validated algorithms for generating perfect hash tables and functions for any given list of tokens? I would be interested in that. And by perfect, I mean the table has no empty slots and there are no collisions of the hash function for the given set of tokens.

Also it would be nice to be able to add this hash generator to the build process to generate a new perfect hash table/function each time the list of tokens is updated.

Thanks in advance.

Firefox 50.0

Posted Nov 16, 2016 17:05 UTC (Wed) by ebassi (subscriber, #54855) [Link]

You should probably have a look at gperf.

Firefox 50.0

Posted Nov 16, 2016 17:08 UTC (Wed) by josh (subscriber, #17465) [Link] (1 responses)

There are well-established algorithms to construct perfect hash tables, with no collisions, given a fixed set of strings. (They don't always avoid every empty slot; it's easier to construct a function that has a small number of empty slots.) For instance, gperf can build such a table.

Firefox 50.0

Posted Nov 16, 2016 21:30 UTC (Wed) by mark625 (guest, #13741) [Link]

Excellent! Thanks to you and ebassi for the gperf reference. It is relevant to my interests.

Firefox 50.0

Posted Nov 16, 2016 17:10 UTC (Wed) by ohrn (guest, #5509) [Link]

Who needs a perfect hash when there is the deterministic acyclic finite state automaton? I just love that name! :)

Here's an example of using it for a similar problem, matching a host name against a set of top level domains:

https://codereview.chromium.org/197183002/

The python generator script has good explanation of how it works. The original gperf hash solution and the list of domains came from Firefox I think.

Firefox 50.0

Posted Dec 6, 2016 8:21 UTC (Tue) by mildred593 (guest, #107325) [Link]

You can also use an ordered tree which would be simpler.

Firefox 50.0

Posted Nov 16, 2016 17:06 UTC (Wed) by jem (subscriber, #24231) [Link]

> It'd actually be a good place for a perfect hash table, built at compile time.

I don't see why it would have to be a perfect hash table. We only need a hash function of type String -> Bool, so it doesn't matter if there are collisions.

Firefox 50.0

Posted Nov 16, 2016 19:22 UTC (Wed) by rgmoore (✭ supporter ✭, #75) [Link] (1 responses)

Building at compile time would be very elegant, but I'm not sure it's the right solution. It might be better to build the list of executable file extensions by looking at a system-provided list, e.g. from the registry in Windows. That would let you adjust automatically to whatever the actual running environment thinks is executable, even if that's updated by something like a software install that adds an executable file type. It would also mean Mozilla wouldn't need to keep the list of executable file types itself, or update its software when somebody introduces a new one.

Firefox 50.0

Posted Nov 17, 2016 8:35 UTC (Thu) by NAR (subscriber, #1313) [Link]

Once I had to chase a bug in some C code. The code crashed reproducably, but the core file was "strange", some registers contained different data than they should have according to the assembly and the memory (or something like that - it was long time ago and I don't remember the details). Anyway, an array of strings became suspicious. It was initialized at startup and never modified later, so I rewrote the code to generate the array at compile time, made it const, hoped that gcc will put the array into read-only memory so I could catch when something tries to modify the array. Needless to say, the bug went away (or at least the code didn't crash anymore at that place). Probably the memory layout did change and what was overwritten before stopped being overwritten. So there might be other advantages of creating a data structure at compile time even if in this case it might be wiser to ask the OS what it thinks is executable.