7 ms·

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

by orf 6y ago

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. Looks like an interesting project though.

Humphrey 6y ago
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.
doovd 6y ago
Indeed, there's nothing O(1) about this and is precisely still O(n) ¯\_(ツ)_/¯
aphextron 6y ago
>Seems like O(n) to me? As the number of files grows, so does the speed of your builds? O(n) effectively approximates O(1) with sufficiently low values of n
- deleted 6y ago
  [deleted]
- adtac 6y ago
  If we're just going to make up new definitions for existing terminology, why even bother discussing anything?
- XCSme 6y ago
  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.
- tylerhou 6y ago
  You have a misunderstanding of O notation. 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_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...
nicoburns 6y ago
I think they might be claiming to be O(number of files changed) rather than O(total number of files) for incremental compiles.
- orf 6y ago
  Probably, but saying “each O(n) change takes O(1)” is a pretty confusing way of putting it.
- elpool2 6y ago
  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.
all-fakes 6y ago
If we're being pedantic, > Some bundlers may even have O(n^2) complexity: as your project grows, your dev environment gets exponentially slower that's clearly not exponential!
- XCSme 6y ago
  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.
- tomc1985 6y ago
  Huh? n-squared is an exponent
  - connor4312 6y ago
    Exponential refers to c^N. N^c is quadratic. Small visualization: https://www.onlinemathlearning.com/image-files/exponential-quadratic-linear.png https://www.onlinemathlearning.com/image-files/exponential-q...
    - mrits 6y ago
      It doesn't help that most people in journalism use the phrase exponential growth to describe quadratic growth.
    - Akangka 6y ago
      We call that polynomial, not quadratic.
      - TomMarius 6y ago
        Both is right, quadratic being subset of polynomial.
  - brokensegue 6y ago
    we call that "quadratic". exponential is when the exponent is variable. (unless I'm being whooshed)
dandelany 6y ago
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?
- renewiltord 6y ago
  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.
- strombofulous 6y ago
  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.
  - dandelany 6y ago
    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
cammil 6y ago
Do they mean O(1) with respect to a change? If you make a change, only one file is rebuilt. Not all of them.
- XCSme 6y ago
  Isn't this how most bundlers work? AFAIK, ParcelJS for example caches results and only updates what changed.
  - renewiltord 6y ago
    That's a good point. The webpack-dev-server also has incremental builds so I don't understand what this does differently.
    - XCSme 6y ago
      I think the difference is that they don't create a bundle but import the files directly in the browser.
gavinray 6y ago
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: https://youtu.be/Yu9zcJJ4Uz0?t=1018 https://youtu.be/Yu9zcJJ4Uz0?t=1018 ---- 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?
- jchook 6y ago
  It’s certainly not O(1). 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.
reissbaker 6y ago
> Seems like O(n) to me? 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.
weego 6y ago
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
wereHamster 6y ago
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.
- sjwright 6y ago
  Cool, I’ve been writing "Isomorphic Javascript" and I didn’t even realise it.
pimterry 6y ago
>> 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)

by orf 6y ago

Humphrey 6y ago

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.

doovd 6y ago

Indeed, there's nothing O(1) about this and is precisely still O(n) ¯\_(ツ)_/¯

aphextron 6y ago

>Seems like O(n) to me? As the number of files grows, so does the speed of your builds? O(n) effectively approximates O(1) with sufficiently low values of n

deleted 6y ago
[deleted]
adtac 6y ago
If we're just going to make up new definitions for existing terminology, why even bother discussing anything?
XCSme 6y ago
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.
tylerhou 6y ago
You have a misunderstanding of O notation. 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_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...

nicoburns 6y ago

I think they might be claiming to be O(number of files changed) rather than O(total number of files) for incremental compiles.

orf 6y ago
Probably, but saying “each O(n) change takes O(1)” is a pretty confusing way of putting it.
elpool2 6y ago
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.

all-fakes 6y ago

If we're being pedantic, > Some bundlers may even have O(n^2) complexity: as your project grows, your dev environment gets exponentially slower that's clearly not exponential!

XCSme 6y ago
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.
tomc1985 6y ago
Huh? n-squared is an exponent
- connor4312 6y ago
  Exponential refers to c^N. N^c is quadratic. Small visualization: https://www.onlinemathlearning.com/image-files/exponential-quadratic-linear.png https://www.onlinemathlearning.com/image-files/exponential-q...
  - mrits 6y ago
    It doesn't help that most people in journalism use the phrase exponential growth to describe quadratic growth.
  - Akangka 6y ago
    We call that polynomial, not quadratic.
    - TomMarius 6y ago
      Both is right, quadratic being subset of polynomial.
- brokensegue 6y ago
  we call that "quadratic". exponential is when the exponent is variable. (unless I'm being whooshed)

dandelany 6y ago

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?

renewiltord 6y ago
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.
strombofulous 6y ago
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.
- dandelany 6y ago
  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

cammil 6y ago

Do they mean O(1) with respect to a change? If you make a change, only one file is rebuilt. Not all of them.

XCSme 6y ago
Isn't this how most bundlers work? AFAIK, ParcelJS for example caches results and only updates what changed.
- renewiltord 6y ago
  That's a good point. The webpack-dev-server also has incremental builds so I don't understand what this does differently.
  - XCSme 6y ago
    I think the difference is that they don't create a bundle but import the files directly in the browser.

gavinray 6y ago

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: https://youtu.be/Yu9zcJJ4Uz0?t=1018 https://youtu.be/Yu9zcJJ4Uz0?t=1018 ---- 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?

jchook 6y ago
It’s certainly not O(1). 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.

reissbaker 6y ago

> Seems like O(n) to me? 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.

weego 6y ago

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

wereHamster 6y ago

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.

sjwright 6y ago
Cool, I’ve been writing "Isomorphic Javascript" and I didn’t even realise it.

pimterry 6y ago

>> 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)