Some of this wording confuses me and should probably be reworked:
> Snowpack is a O(1) build system… Every file goes through a linear input -> build -> output build pipeline
Seems like O(n) to me?
> Snowpack starts up in less than 50ms. That’s no typo: 50 milliseconds or less. On your very first page load, Snowpack builds your first requested files and then caches them for future use
So you can open a socket in 50ms? Seems disingenuous to imply anything takes 50ms when really you’re just waiting until the first request to do anything.
I watched the talk linked by Ives, the guy behind Codesandbox.
So the exact quote in that talk, is:
"... and if you take the existing module map (file), it essentially replaces (function) #1 with this (new) one. And this is how bundlers like Metro work, for example -- They regenerate the file, and over a websocket connection, they send the new file and say "replace function #1 with this one, and execute it."
He then touches on how bundlers do a lot more than just transformation in this step, other processes like chunking, tree-shaking, code-splitting, etc. And this makes it incredibly difficult to properly cache a file, because you can't really get a good heuristic for diffing/patching.
And then the quote of the hour:
"But what if bundling had an O complexity of 1? That would mean that if one file changes, we only transform THAT file and send it to the browser." (no others in dependency tree)
Above quotes start here, and go for about 2 minutes:
In this context, what I believe Ives is aiming for is the idea that's pervasive throughout the talk, which is this "50ms or second HMR time."
If you overlook slight variances between time to update a file which contains more/less content with this system, and you average it out to "50ms, every file, any file", I think that would qualify as O(1) bundling/hot-reloading right?
However I think the intuition and excitement exists around the ideal bundler and I think this project provides hard evidence that we can strive for such things with incremental success.
Maybe I'm misunderstanding, but it seems clear to me: Other bundlers = change one file, `n` files are rebuilt/bundled. Snowpack = change one file, only that one file is rebuilt. Building "from scratch" will necessarily be O(n), but incremental rebuilds can be O(1), no?
An incremental rebuild will still be O(n), but in this case n=1. This isn't the same as O(1) where, regardless of the input size, the number of operations will remain the same. This isn't just being pedantic, O(1) implies they have a seperate algorithm that doesn't grow as input size grows, which is totally seperate from intelligently running an algorithm whose runtime increases at a constant rate. While in this case the resulting runtime will be the same, the nuances that are implicitly implied when they say something is O(1) will not be true.
Surely that depends on what you call `n`, they are using `n` to refer to the number of files in the project.
I would agree that the term is a bit of "shorthand" that doesn't perfectly map to the idea of big-O complexity - for exactly the reason you mention, build time still depends on the size of the file. But for me, it was shorthand that helped me understand the idea. They had two other options on how to write this - either leave out the big-O stuff entirely, or explain it more deeply eg. "most bundlers are O(lmn) where l is the number of files, m is the number of files changed, n is the number of JS tokens per file" or something. Both of these options may have been more "technically correct" but would've taken me longer to grok the idea than the way they have it written. Maybe they should just have a footnote for the pedants explaining that O(1) is more of an idiom than a technical claim in this case :P
Yes, exactly. O(n) means that as n (the number of files in the projects) grows, so does the runtime complexity. O(1) means that as n grows, the runtime complexity remains constant. In this case, they're always using an input of size n=1, but this doesn't make the algorithm itself O(1). By calling this an O(1) operation, they imply that you could rebuild your entire project at the same rate you can rebuild a project with just one file changed. This is misleading and untrue, which is why it's not peedantic.
It wouldn't be a problem if it wasn't on a technical page like this where this distinction can have large implications (such as the one above). When I read that it was O(1) I drew conclusions that were both very favorable to snowpack and also completly untrue. It'd be like if you said you drove a truck but you actually drove an accord. It's probably fine to say that 99% of the time, but it could cause issues if you say it to your mechanic because they'll conclude things from what you said that might not be accurate.
If you have a project with 1000 files in it, how often are you editing all 1000 of them at the same time? Virtually never from my experience.
The way they've structured "rebuilds" is to only "build" (or really probably do very little if anything) to just that one file you edited and saved.
Yes if you edit all 1000 files it's going to take longer.
"In theory there's no difference between theory and practice. In practice, there is." I think this is one of those cases where in practice it's awfully close to O(1) so while they're technically incorrect practically it's difficult to tell the difference.
This esp. compared with something like Angular in which you're looking at many, many seconds of build time to get started. I think it's laudable.
> If you have a project with 1000 files in it, how often are you editing all 1000 of them at the same time? Virtually never from my experience.
For the purposes of Big-O notation, this does not matter. If they didn't need its semantics, they should not have used the notation. Simple as that.
It's still O(n), regardless of the fact that they have optimized constants and in the best case it may be less than that. Irrelevant. Big O establishes an upper bound. Bubble sort is still bubble sort, we don't care if it is quick when you are ordering two elements.
Maybe they meant to advertise Ω(1) on the best case, and compared to other build systems?
EDIT: another poster says that "n" refers to the number of files in the project. Still misleading. Usually we are interested in how the complexity grows as the number of inputs grow. Big O purposely discards constants.
They could say that other build systems are O(n) where n is the total number of files, while this one is O(n) where n is the number of modified files. It's immediately clear then how this is better for the build use-case, while still making it clear how the efficient it is as the input size grows.
> They could say that other build systems are O(n) where n is the total number of files, while this one is O(n) where n is the number of modified files. It's immediately clear then how this is better for the build use-case, while still making it clear how the efficient it is as the input size grows.
That's a great, concise and clear articulation. The project would do well to quote you on that!
If anyone's still struggling with the difference between O(1) and O(n), there's a common example with lists that might help:
1. Getting the head of a list is usually O(1). It doesn't matter how long the list is, getting the head element always takes the same amount of time.
2. Getting the length of a list is usually O(n). The time taken to count the list entries grows in proportion with the length of the list.
As an aside, note also that a list with a single entry doesn't make the length function O(1).
It's only misleading if you take it out of context and examine that one sentence without reading the rest of the article. It's perfectly clear what they mean in the post (to me, at least).
> An incremental rebuild will still be O(n), but in this case n=1.
TFA explains pretty clearly what claim is being made. They're talking about the cost of rebuilding one file, given the "input" of a project with n files. They claim that for other build systems that cost (the cost of one file) scales linearly with total project size, but for theirs it doesn't.
Your objection here redefines n to be the number of files changed, but they don't claim anything about that.
They didn't claim anything about the cost of changing multiple files. "Rebuild one file, in a project of size n" is the operation they're examining the performance of.
There is such a thing as best-case, worst-case, and average-case computational complexity.
Also in this case complexity we seem to care about is function of two factors: number of files and number of changed files. Call the first one n and the second one p.
The complexity of webpack would be O(n) + O(p) [+] and the complexity of snowpack would be O(p) in development. Worst case p = n, but best case p = 1, and usually in development p is on average very close to 1. Also p is parallelisable, making it appear like p = 1 WRT wall clock time for small p values even though CPU time would be O(p).
[+]: which one of the p or n constant factors dominates is unclear, but some hardly parallelizable n-bound processing is always present for webpack.
Yeah, I thought it was easy to understand. Single file builds are O(1) in the number of files in the project. This is probably better described as "incremental compilation" or some variant, though.
I think other bundlers/build systems can also do incremental builds (although may be implemented as modules in some systems, and not part of the default system)
for example, lastrun in gulp (which is part of the default)
>> Snowpack is a O(1) build system… Every file goes through a linear input -> build -> output build pipeline
> Seems like O(n) to me?
Big O notation describes how for a given operation (sorting a list), a given measurement (e.g. items compared, memory used, CPU cycles) grows in relation to a set of variables describing the input to the operation (number of elements).
Here their operation is 'a single-file incremental compilation', they're measuring how many files need recompiling in total, and the only variable n is 'the number of files in the project'.
In that case, Snowpack is O(1), and most other bundlers are O(n). They're not wrong.
You can argue that that's not an interesting point, or that there's other measurements that matter more ofc. It's not wrong though, and imo incremental single-file changes are a thing you care about here, and only ever processing one file in doing so is an interesting distinction between Snowpack and other bundlers.
Big O notation is not (ever) defining any detail of the operation in terms of every possible conflating variable. All Big O comparisons include implicit definitions: the exact same sorting algorithm could be described as both O(nlogn) for item comparisons required per n items in the list, or O(kn^2) for memory copies required per k bytes of largest item & n items, and both are accurate & useful descriptions.
(Sorry to be pedantic, but there's a _lot_ of replies here that have misunderstood big O entirely)
Yeah, but no one really says "quadratically slower" in the real world, while "exponentially slower" is used by regular non-CS/math/stats people. It's a forgivable inaccuracy.
Maybe we are mean and they are right, who knows: they said "exponentially slower", which might be true if somehow executing the instructions of the O(N^2) code runs in O(2^N) time due to CPU/RAM/disk limitations.
Indeed. It's been a while since I've had to so much as think about big O notation and I forgot that quirk. To most folks "exponential" means n^2 or greater
When family talks to me about covid spreading exponentially I am pretty sure they mean n times n, or n^2
Yes we all know the technical definitions with respect to software and algorithmic complexity. But the lack of sympathy/empathy on display with how a common definition of a word can be misconstrued by someone without an academic background in tech is kind of surprising (ok well maybe not so surprising but c'mon folks, we are all human)
The JS community doesn't give a fuck about using correct technical terms. It's like listening to a 5yo child trying to use adult words, you have to know to interpret them differently.
"Isomorphic Javascript" ~ Same code running in browser and server, has nothing to do with isomorphism in the mathematical sense.
"O(1) build system" ~ It's faster than others, has nothing to do with big-O notation.
I just have no idea why someone would think the killer feature of a new new new new new build system for web dev is micro optimising for speed.
The issue with build systems is complexity, poor defaults, poor config systems that often have you reading across the docs for multiple build frameworks they mashed together trying to figure out how to merge config overrides and breaking changes between versions.
Literally the last thing I care about is whether my browser has refreshed fractionally quicker as I switch from my IDE
Sort of. What they're talking about is the time it takes to rebuild during your dev-cycle, when you will typically be editing 1 or 2 typescript files and then refreshing your browser. In this case N is the total number of files in the project. Other bundlers will be O(n) because they need to bundle all N files together (higher values of N result in longer build time). While Snowpack will still be O(1) because the time it takes to rebuild the 1 or 2 files you edited does not increase with the value of N.
I believe they are saying O(1) since it only builds the single file that you just changed and will never just build all your files. They also mention that it only builds the files as requested by the browser, so in terms of the compiler it would be O(1), however it would effectly become O(n) the first time you use it if you include all the individual requests the browser makes as a single unit.
Yep, it's very much O(n). Even if you only consider incremental compilation it's O(n), where n is the number of lines in the file being compiled.
That being said, I understand the feeling of it being sort of O(1) from an incremental compilation perspective. For most of the JS build ecosystem, changing a file can result in many, many files getting recompiled due to bundling. So if you ignore that the size of the file isn't constant, it seems kind-of-O(1) for incremental compilation: for any file change in your codebase, only a single file gets recompiled, regardless of the size or dependency structure of the codebase. And as a result it should be much faster than the rest of the JS ecosystem for incremental compilation, since typically individual files don't get to be that large, and other incremental build systems may have to compile many files for a line change.
But yeah, from a CompSci perspective, it's O(n), even for incremental builds: as the number of lines of the file grows, the amount of work grows. And for non-incremental builds it's of course O(n).
> So you can open a socket in 50ms? Seems disingenuous to imply anything takes 50ms when really you’re just waiting until the first request to do anything.
This makes a lot more sense in the context of the rest of the JS ecosystem. Of course, what Snowpack is doing is opening a socket, and opening a socket in 50ms isn't particularly impressive (mostly it's just measuring the overhead of starting a Node process and importing various dependencies). But other JS ecosystem build tools are very slow to start, because they're architected differently than Snowpack: they do full builds of the entire codebase (due to bundling) — or at least typically builds of large swaths of the codebase — and so on startup typically they'll immediately start building because doing it just-in-time is slow, which makes them slow to start. And if they don't start building immediately, the first request they service is typically quite slow. Since Snowpack doesn't bundle files, it's able to only build the files a specific page uses, which is typically much faster than building the entire codebase; as a result, they can do on-demand builds when a specific page is requested instead of relying on precompilation.
The 50ms isn't impressive in terms of "look how fast we opened a socket." It's impressive in terms of "look how quickly you can start loading pages to see results as compared to other systems," because their build system is so fast that they don't need to precompile.
When we say O(n), we say that as n goes towards to infinity, the runtime grows as k * n, where k is some constant.
Your sentence effectively says:
> (k * n runtime as n approaches infinity) effectively approximates (j runtime as n approaches infinity) for sufficiently low values of n.
This makes no sense, because you can't have n approach infinity and also be a "sufficiently low value" at the same time.
I think what you were trying to say is that O(n) algorithms run in constant time (or "fast enough") given a constant input size. But in that case, O notation is meaningless because when we use it, we specifically care about what happens at infinity.
Also, O(1) isn't synonymous with "fast enough"; constant factors can matter a lot. For example, the "fastest" (Big O wise) matrix multiply algorithm has such a large constant factor that using it is not feasible for matrices that fit on today's computers. https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...
I think you confused some definitions, what you are saying sometimes applies for O(constant), for example you can consider O(57) to be O(1), if the number "57" never changes even though the input size changes.
O(n) by defition means that execution time grows lineary with input size.
> Snowpack is a O(1) build system… Every file goes through a linear input -> build -> output build pipeline
Seems like O(n) to me?
> Snowpack starts up in less than 50ms. That’s no typo: 50 milliseconds or less. On your very first page load, Snowpack builds your first requested files and then caches them for future use
So you can open a socket in 50ms? Seems disingenuous to imply anything takes 50ms when really you’re just waiting until the first request to do anything.
Looks like an interesting project though.