1000x FASTER JavaScript?
Вставка
- Опубліковано 6 кві 2023
- Recorded live on twitch, GET IN
/ theprimeagen
Original: jpcamara.com/2023/03/07/makin...
MY MAIN YT CHANNEL: Has well edited engineering videos
/ theprimeagen
Discord
/ discord - Наука та технологія
It is so incredible how Prime can absorb and explain code instantly, how good he is at recognising and understanding the nuance of what's going on.
And right on the next line stumbles on the simplest english sentence
i... uh... i have my strengths and weaknesses :)
imagine saying that you are limited by the 4GHz processor making webapp to the computer scientist from the past that works with punch cards and 5Hz light bulb computer
I always recall the story of Ken Thompson making grep. Lee McMahon was working on a Text Analysis project from "The Federalist papers". McMahon wanted to find the occurrences of words in the documents, all 85 documents were just over 1MB which at the time was too much to fit in ed (editor). Ken went home for dinner and the next day brought back grep.
Well they didn't have JavaScript back then
@@hammerheadcorvette4 gigachad
@@hammerheadcorvette4 there's a video of Brian Kernighan interviewing Ken Thompson here on UA-cam. Ken admits to have had this as a personal project prior to their conversation, and used this as a excuse to finish it up.
"lightbulb computer"
This video has taught me so much and forever changed the way I look at the spread operator. Your commentary with your expertise also adds a lot of things I wouldn’t catch if I had read the article myself. Thanks a bunch
This is just one of those things if you work with JavaScript you are so far detached from everything it can be easy to go for the flashy modern syntax instead of thinking about the actual memory allocations happening. I don't do anything as low level as C but in Golang I know that preallocating a fixed array will always be quicker and if I do need to create a dynamic array then I also know that everytime an append operation is called then the memory is doubled to prevent multiple re-allocations
This is what happens when you're detached from whats going on under the hood.
He didn't push because the syntax sugar looked cooler/cleaner to him, guaranteed.
yepppers
The thing is that mutations are just prohibited if you learn React from the docs
@@BlackDragon-tf6rv yeah but they're only prohibited as part of an object's (top-level) state; there isn't any rule against mutating anything that never gets passed to useState
@@Starwort but it seems this was part of the react state, hence why immer was part of the solution.
@@BlackDragon-tf6rv if your react code is looping over 50k items youre doing it wrong
If you want to write functional code, use a functional language that was designed for it. Immutable JavaScript is an anchor and the language wasn't designed for it.
Despite lists being immutable In a language like Elixir or Clojure, it won't copy the whole list every time you add something to it - because the language was built around immutability the libraries can take advantage of structural sharing. When you add an element to a list 50k long, it doesn't construct a whole new list with 50,001 elements, it re-uses the 50k list and adds a new node. Other variables referencing the 50k list will still only see the 50k elements.
This is safe in these languages because no other code can change that 50k list out from under you.
This!
Probably V8 could optimize for these scenarios in the future(although extremely unlikely as it is extremely hard to do it for non functional languages)
but currently, forcing immutability in JS will likely result in performance issues.
Exactly This!
@@avid459 A compiler can only do as much. If you request a mutable array slice out of another mutable array it pretty much has to copy the memory. Introducing some weird copy-on-write functionality would add so much complexity that more sane and more popular scenarios would all of a sudden get way way slower. The only way this could be optimized is by introducing explicitly immutable types, but that would require reworking the entire type system and probably cause compatibility issues.
I do agree with your points in that Javascript originally wasn't designed for immutability and therefore writing immutable code is almost always at the cost of performance. But that doesn't seem to be the issue in this case. The groupBy function took a list of rows as an argument and returned a new map. For each resKey in the map a new array was created and rows were added to it. So using [...previous, row] was completely unnecessary since the original list of rows was never mutated. The groupBy function was (kind of) already immutable since it didn't modify data from outside the function.
This was simply bad code.
I have zero issues writing functional code in Javascript.
1000x returns
just like the stonk market
the stack market
Lesson: don't trust JavaScript's sugarcoated syntax
never
It did exactly what you would expect. Problem is not Javascript, is the memory allocation of large chunks of data. This would be slow in any language.
Or python. Or any dynamic and/or GC language. People don't realize how much difference preallocating an array vs braindead push makes.
It's incredible how much one learns from primagen screaming
14:55 is always me whenever i code review
In functional languages immutable patterns can be faster. Since the runtime knows that nothing else can change the list it will can share common data between different "versions" of the list
js is not such a language
@@kippers12isOG JS is a functional language, just not in the same way Haskell is.
I started a library of functions intended to be "Pure", but eventually this library just turned into a bunch of handy functions that "might" be immutable. For any heavily used function it is always far too expensive to shun mutation.
Also, the most challenging function I added was a mergeObjects, but the cool thing is it is also a cloneObject since you are just merging an existing object onto a new empty object.
merge object is a great exercise!
all TV devices run my code, mergeObjectDeep, that prevents us from using lodash, but instead i hand rolled it :) (2018)
@@ThePrimeTimeagenguys he works at Netflix btw!
24:51 "pushing into it over and over again". That's exactly what amortized means
Very helpful breakdown! I find most of Prime's videos quality entertainment but the ones where he explains technical things are my favorite. I don't do as much Javascript but I feel like the same memory concepts would transfer to python and data heavy pandas operations. It's easy to get tempted to use some snazzy one liner without realizing you're going to enter into a world of hurt later on haha. And love the advice at the end, just need to endeavour to learn one level deeper about what you're doing, so helpful. Thanks Prime!
The problem is that people want functional features in JS. The JS compiler doesn't have the optimizations (or the required information to perform those optimizations) to avoid allocating.
learned something new thank you moustache man
"You don't have to go all in, just a little deeper" - that's what she said.
This is awesome to be talked through, more optimisation content is extremely welcome
This video was super informational, please do more like these on Javascript / React! Thank you!
This is wild, I feel like my generation of cs grads was taught 'generic abstractions at all costs' but now that functional js is more mainstream it seems like its now 'immutability at all costs'. I hope someday this career becomes a real trade instead of the road to mastery literally only being the unlearning previously help truisms.
This is why every [js] programmer needs to know C/C++ and maybe a touch of assembly. This whole video is the first thing you learn when using C++ vectors.
there is people on the internet have pointed this out so you don't need to xD
Could not agree more. This is just sad
This isn't really about C/C++ at all. Unneccessary copying and a disregard for algorithmic complexity has very little to do with those languages really. Sure, C++ move scemantics is all about reducing copies. But it's not in this context.
The problem here is the GC and hiding operations. It teaches people (and GC advocates often argue for this point) to not think about memory or what the code is doing, just how easy it is to write. Whoever wrote that code would never write the explicitly allocating & memcopying version of this code I'm 100% sure, figuring out something better is a more attractive way to program. But javascript makes it very easy to do it. If the allocations in the spread were the only concern C++ doesn't even teach to handle this situation well becuase you could easily have similar strucutres in C++ with RAII cleaning up after you.
I don't think any programming language helps with teaching you to not throw around data like this other than the friction it introduces, so you don't do it in that language. But to keep up the healthy constraints on allocation and hiding how expensive operations can be you need to understand what you're doing in the languages which make it easy to do these expensive operations. It's just something that needs to be taught directly. I'm pretty sure that's why the author of this article goes through so many possible solutions, just to have an oppurtunity to teach the audience these issues and to think about the cost of the operations they're asking for.
Kinda but this is more just completely ignoring efficiency lol. But you’re right learning C++ probably would build more thought towards that in the first place. Most JS developers never even consider this stuff
I learned a bit of C++ lately and have been building some projects using it, definitely a must. You would be surprised by how much control you have over the memory and how much other languages try to make you ignorant about this.
Back then when I developed image processing I discovered that some code worked faster on processor X while the other one worked faster in processor Y.
My solution to always have the fastest speed no matter what processor you run on was to have all optimized codes compiled and during startup of the application "measure" which variation was the fastest.
In order to know which code worked faster or not I always had a reference function that is human readable and easy to understand. That reference function was used to measure the speed but also created an end-result that I could test my optimized function to it. Some functions got even at assembly level optimized for some processors.
I hate reduce not just because it's performance issues but because most of time it's unreadable mess. And every time I'm trying to bring it up to people who write reduce they just shoot back that readability is subjective. And whole functional thing. If your function doesn't modify arguments and doesn't do side effects then it'salready 100% functional. You can't make it even more functional by throwing in reduce and friends in it.
this is such facts, reduce is 99% of the time one of the worst
Bro these videos are so good to watch. Its definitely entertaining and educational at the same time... keep up this perf content. Straight fire boss daddy ;)
the main issue with immutability is thanks to React, as when you are managing arrays or objects mutating directly may cause the components to not update so its not clear to a dev when "wait so using immutability everywhere is bad?". In this case you have a reduce which creates a new array so it works but then because you still are thinking in React "oh yeah its easier to create a copy to ensure the data is not changed!" and you just loaded the foot gun.
Yeah, it's really easy to get into the habit of thinking immutability === good when working with react, because it's so common to hit annoying bugs if you go to mutations by default.
one more: learning a programming language that doesn't uses GC really helps a lot as well. Nice video!
I also had 10% speed performance gain when doing image processing when you process data with the size of your L2 CPU cache sizes. If a cache line was 32 bytes then I would only move 32 bytes from DRAM (32 byte aligned) and do the processing on it, then next 32 bytes and do the next processing on it.... This increased the chance that data was in the L2 CPU cache line and you gained speed that it did not have to reload from DRAM. Your code becomes more complex but you gain speed.
That sounds pretty low level to me, or does it? Is this something implementable in Go or Java, or you have to get down to Rust/C level?
@@dejangegic This was in C++ 20 years ago but probably still valid with modern CPU's.
Back in those days the clients wanted the fastest processing. So being faster than the competition meant the difference between selling and not selling.
There's an additional performance hole with the built-in array methods, though.
Map/Filter/Find/etc handle sparse arrays in interesting ways (they skip over unset indices). It adds extra overhead to check, even if the array is dense. Additionally, it needs to apply `this` (for people into those things).
Handwritten map/reduce can (or could in the past; who knows what v8 is doing these days) be significantly faster than the built-in (can initialize to known size, skip sparse checks, skip application of `this`, et cetera).
It's still not going to beat indexed access and mutation, of course, but it does make a non-trivial dent.
There are other techniques for limiting memory creation while using declarative, immutable patterns, as well (like transducers, which could take a whole chain of map/filter and boil it down to creating only one new dynamically sized array).
And personally, I would generally prefer to have teams hit performance issues with immutability than hit data corruption / leaking / runtime exceptions with shared data that should not have been shared (an example might be having a pointer to a globally accessible "sessiondata" variable that is mutated during the span of each connection, that isn't cleaned between each connection). Both are examples of bad understanding of the workings of the system, but if the code is going to be hyperbolically bad in some way, I would much rather have the team improve the performance of safe and correct data, than improve the safety and correctness of blazingly fast data.
The telling sign that there shouldn’t even be a .reduce, is that you are taking a map object, mutating it, and returning the same object back from the closure into the next iteration.
I mean, if you are producing “value types” from reduce, it is fine. Abusing reduce for the looping nature of it, is just plainly bad code.
About the results at the beginning, from the simple-test. I speculate that .reduce is faster for small arrays, because the JIT hadn’t had enough time and data to do its magic on the sum-loop. Since the reduce loop is done in CPP-land, it may be faster for one-off calls, since interpreting every instruction of base-level interpreter (v8 ignition) in a tight loop is not ideal.
I don’t really know why calls to array methods aren’t getting replaced by bytecode intrinsics. I feel like that way JIT can potentially see through the .reduce and eliminate closure allocation and function call altogether (inline the callback into the loop body). Have to see how JSCore (WebKits engine) deals with those. I’m hopeful because of abundant use of array methods, those should be heavily optimized down to “hand written” for loops.
Anyway debugging generated v8/JSCore bytecode and native assembly is hella troublesome. Someday, I will. Not today tho. Not even tomorrow.
Don't worry there isa video coming
I love this channel. Very humbling. Every time I tell myself "I'm a good dev" I watch an episode to realize I don't know anything.
If Dr Disrespect was a coder. Loved the video :)
Typical SV startup React/JS dev pleb reporting in. I am loving your videos! They have really got me to think more critically about how I approach my own code and the impact memory and trash management can have. I've been historically blessed with fast CPUs used by customers and products that do not require memory intensive actions, but as I have begun working on larger scale applications it is starting to show up more and more. I actually started with C++ (way back in the day) before moving to Web Development and your videos have pushed me to want to get back into lower level languages. I even installed Rust recently and have been playing around with it! Anyways, thank you for the funny and poignant videos.
Immer is a godsend for managing state in React - that's the main use-case for it because you can't mutate state directly or it's gonna complain.
p.s.: however I think something like this should work fine.
const [state,setState]=useState([1,2,3]);
setState(state=>{state.push(4); return state})
p.s.s.: i'm wrong in my p.s. lol
this is not going to work, react not going to do anything, since it only checks the reference diff of the state (array), since you modified the array instead of creating a new one (new reference), react don't see any reference change. so no update
@@dulanjala yeah, you're correct. I thought for whatever reason that setState(x=>x) triggers a re-render even if the value's the same.
Never do Array.from(x).map(fn). It creates an extra temporary array. If you have to do that then use the second parameter. i.e. Array.from(x, fn). This avoid the intermediate array.
I think in React, you're often told to not mutate state. I initially tried to do this and realize the changes weren't being reflected and then noticed it was recommended to recreate state and changing state directly wasn't considered safe
Hi @ThePrimeTime, what an awesome video, I love Javascript so much, it is because it is the only programming language I know so far, I am still looking for some knowledge about improving performance in JS, I found this vide, it's really2 helpful. Since I learn all programming stuffs by myself from youtube and article, I found it a bit hard to look for how to optimize the code performance especially in JS. I wish someday, you ll consider manking some tips or at least a mini roadmap on How to Do better javascript (I mean in performance). Thanks again
Something else I also remember in gaining speed:
Prepare the data that you want to process so that it only will contain code in the if-else part and never in the else-end part.
The else-end part actually should not exist in your code.
The code in else-end will create a jump and your CPU branch prediction will need to be reloaded from DRAM.
So before you enter the for loop you only have pure data that cannot go wrong and memory aligned according to your processor need. Any data that could go wrong should be removed before you enter big calculation loop.
Of course this messes up your human easy readability code 🙂shocking people that love clean code :-) :-)
I don't think that's how branch prediction works
@@themisir The CPU preloads instructions from DRAM into the processor. If you end up in the end-else part then it is an unexpected jump and all preloded instructions must be reloaded from DRAM.
Look at how the instructions are turned into assembler instructions. Normal the if-else part avoids jumps.
Thank you Prime for opening my eyes to these things ❤
"It's good because it's immutable" sounds like some kind of a weird slogan that a crypto bro would say.
The problem with pushing is array can be borrowed somewhere when we're modifying it. As for me, is the better to scan map, count total capacity of groups and then create an array with that capacity (not sure that js allowing it), then just extend those arrays with capacities by values (not sure that this operation can be done in js). The alternative way is to write out somewhere (maybe in jsdoc for this function), that arrays of map can be modified during execution - so nobody gets wonder
Can't wait for the next "blazinging fast" video!!
Sometimes i think im a bad programmer, but then i look at professional javascript programmers and i feel like a genius
> 25:48 reduce is atomic, so you don't need to worry about the mutations done inside it
Ooh, I get to nitpick on the internet!
I would think the reason not to worry is that the only objects that get mutated are objects created by the function that calls reduce, and the data never escapes from its scope.
In rust terms, the function that calls reduce _owns_ the map and all the arrays inside it, and the borrow checker would not complain. But you could not create a mutable iterator before the reduce and then use it after the reduce without the borrow checker complaining, even though reduce is atomic (by which I assume you mean that it's guaranteed to terminate).
Something else I learned back then when I did image processing was that moving memory from DRAM to CPU cache memory was very slow. You must write your code in such a way that your data you do processing on is only loaded/written from DRAM once and the do multiple operations on that loaded data.
So I created a method A that does processing A
I had a method B that does processing B
I had a method C that does processing C.
So for speed I also created methods AB, AC, BC and ABC that does the processing on the byte so I only move it in DRAM once.
I need someone to actually explain this obsession with immutability in the react world.
from what i understand, react tries to minimize unnecessary renders by using its virtual dom to update only the changes necessary rather than re rendering a whole section because of a change in that code portion. So the components have states and that state will be the basis for re render only if the state changes. React will compare the state to see what changed and update those.
React uses shallow comparison to know when to rerender a component, so when you have arrays or objects as state, if you arent using immutability the component might not rerender properly as the object/array is the "same", so to ensure everything always updates when you want welp, a react dev will normally just default of ensuring you are working on copies instead of mutating objects or arrays directly.
React checks for the reference before deciding whether dataset should trigger re-render or not.
This guy is inspirational.
"To Know these things is really important ..."
- As I'm thinking I don't want to know these things.
I literally wrote a groupBy function yesterday, and it was the for loop and push version.
But I do often default to spread, I assume I didn't there because I write a lot of Rust, and I must have inserted the &mut I'm my head!
My 50 cents, that table was thought to be used in conjunction with stuff such as stores. When you have a store and try to pass data by reference you suffer a lot.
When you accidentally _commit_ a memory in JavaScript.
Just learned a new thing , really doing this without giving a thought.
The more I learn about functional programming, the more I am convinced people who swear by it do not even comprehend the notion of passing by reference.
I´m gonna rewatch this with a friend later. Each time you say "JUT PUSH!!!!" we gonna drink.
I totally agree about mutating. It's one of the things I just can't accept about pure functional programming. With a sufficiently advanced JIT or compiler extremely non-optimal code like this could be compiled into code that not only matches the performance of the mutable version but could very well lead to identical assembly code and there are techniques to use trees to store diffs of immutable data structures that would be similar in speed to mutating... but why! forget about reduce being an atomic function if the variable is created inside a function the only way for other code to have conflicts with its mutations would be to have wild pointers that randomly grabbed the same part of the heap which isn't even possible in javascript unless the interpreter loses it's mind with some sort of crazy bug. I love functional style and I feel reading about it made me a better coder but the complete abandonment of any mutable data is crazy town for no reason. I have similar thoughts about people who want to use recursion everywhere.... Just because a compiler or interpreter can do something for you doesn't mean it's the best place for the work to be done and just because it's more work for the compiler doesn't mean it actually makes a programmer's life easier. Is it so much to ask for a programmer to be able to think through simple loops?
02:08 storing length in variable and using that is slightly faster with big array:
```
function sum(arr){
let sum=0;
for(let i=0,l=arr.length;i
"avoiding mutations" sounds way smarter than COPY FU**ING EVERYTHING
The stack grows downwards, so to allocate stack space you subtract from the stack pointer
Primeagen, I love your videos, and learn a lot with each one, including this one. That being said, I _think_ the point about memory waste, garbage collection, and the impact that has on performance is a bit misleading in this case since the largest performance issue is almost certainly the time complexity related to using the spread operator in that reduce example. I agree with all the points about using mutation inside of a reduce's callback function, but feel that there was a missed opportunity to teach folks about how the spread operator creates a nested loop. To be fair, you did mention nested loops being an issue, but IMO, I'd imagine that many folks took home the idea that the performance improvement was around preventing the garbage collector from running unnecessarily, when the main performance improvement was improving the time complexity of the reducer. Please correct me if I'm wrong here, and thanks for all your content!
Great vid. I don't understand the pushback on .push being O(1) though. It is most definitely is O(1) amortized. Since it's done in a loop, the loop would be O(n), but push itself is O(1). If this isn't actually the case, Imma freak tf out.
>the mutable pattern is good because we don't mutate values
>mutate values using set key
Brilliant, truly progidious
19:32 Sounds like Adam Ragusea making French Macarons. Watch that video and it will make sense.
The for loop runs even faster if you move the `arr.length` out of the loop.
I thought your were going to break out and sing Salt-N-Pepa - Push It song. Loved your video. I subscribed to your channel because of your helpful comments. I look forward to learning how to push it. Push it real good.
You can immediately tell the programmer has never written in anything except JavaScript for most of their career when you read code like that. Once I saw someone calling arr.slice().sort((a,b) => a < b) and not assigning that to anything and then keep using arr later expecting it to be sorted... 😂
To me, the issue presented reduces to not RTFM'ing. 😅 happens a lot when you learn programming from tutorials.
I learn more watching this video, than in my whole 5 years in the university
js is pretty weird. I compared underscore reduce to a for loop for adding a million numbers in a preallocated array and reduce won by about 20% in chrome console. It wasn't until I used the so called byte array version of allocation that the for loop won, by about 5x. That makes sense since we're no longer looping over pointers to random spots in memory but I still find it odd reduce gets optimised by the jit and the for loop for some reason less so. maybe because it gets parallelized :shrug:
What if we in react and want to use setState to push a value into an array?
ChatGPT 4 got it solved in 10seconds. 1000x faster than any debugging session… just paste the code and ask for optimization. Result:
Yes, I can help you optimize the code. One possible optimization is to avoid creating a new array and spreading the old one in every iteration. You can directly push the new element to the existing array, which should be more efficient.
Good Lord. WHY! why! would you not use a simple .push in the first place. Which madness, brings one to think that copy the array for each new element. WHY?!
WHY!!!!! POR QUE MARIA!!!
this is the problem of "modern js," syntax is so damn convenient that people forget what it does
Good to know!!
Its funny because it is actually the recommended way to push items to an array in svelte 😂. great video!
Most people use `arr.push(x); arr = arr;`
Prime, did you notice that Tanner pimped your Frontend Masters course at the end of that article? The link is literally behind your head in the video at 28:00!
WHAT THE HECK IS IMMER
exactly what my reaction when i first discover it!
26:16 except cpython:
```
from time import perf_counter
b=bytearray(100*1024*1024)
t=perf_counter()
for i,x in enumerate(b):b[i]=x^11
print(perf_counter()-t)
```
prints 12.95649664299981
```
from time import perf_counter
b=bytearray(100*1024*1024)
t=perf_counter()
b=bytearray(x^11 for x in b)
print(perf_counter()-t)
```
prints 3.6214119140004186
Where can I read these articles?
Every JS developer (like me) should watch primeagen. Or we will see our end in near time.
20:46 previous.concat(row) and previous.concat([row]) are different if row is array
The speed at which Prime recognised the problem speaks loads about the calibre of the programmer he is!!! #ProgrammingGod 🧎🧎🧎
just a dude
@@ThePrimeTimeagen You should do some videos where you check the code of popular libraries like the one in the video and make them BLAZING FAST by changing a line.😉😉
That would be epic! Think about how many projects would get free perf upgrades from a Prime series haha!🔥
So true we do write a lot of extra stuff for go
Immutability is just a buzzword at this point. You only start to hear it when everyone have the latest cpu on the market. Because it's definitely a performance killer. Probably 80% of cases immutability is not necessary.
First, he was creating the array so why he was cautious about mutation
Second, he had access to the map above so why didn't he use a simple `forEach` instead of `reduce`?
Thanks for the content, btw. Really appreciate. your takes and explanations on the articles help me understand better and learn more.
what's the wallpaper you used at 1:55?
Also what I wanted to know. Did you find out yet?
Conclusion > JP Camara didn't speed up Javascript by 3 magnitudes.
was doing something like this on c# using up more than 20gb of ram, just put my data in sqlite and implemented logic as a query, ended up using less than 100 mb andtaking seconds instead of 17+ minutes
mutations r faster to the point that that one functional language that tries to be optimised (roc) tries to add mutation to your code whenever its equivalent as a compiler optimisation (even though you cant mutate with 'pure functional' principles)
Not really, in functional languages mutability comes at a cost as the compiler cant optiñize a lor fo stuff. Ocml for example can optimise a lof when working with arrays (linked lists in ocml) by knowing that the data is immutable
what a great article
You have to run your tests in separate files if you want a fair comparison.
Isn't the whole reason why push wasn't used in the first place is that React doesn't allow mutating state?
Prime isn't using Ubuntu Mono any more, what's this font?
14:52 got me 🤣 Prime was right without even reading the post, could have ended the video within the first min!
Other funny thing about performance how global/local vars affect the speed. And sadly it's not in favor of local scope
I'm a Java programmer for 10 years. I'm barely familiar with JavaScript and cant believe this problem is a thing, it was solved decades ago in many languages... Why in JavaScript it still exists...
I totally get why "Mutate!" isn't the desirable answer, particularly when giving the functional treatment. There's an argument in favor of internal mutability that should be acceptable to the functional folks, despite the aesthetic pain.
welp I guess I'll finish the CS50 course
Imagine having Prime as your pair. "Gosh, don't spread it, just push it! what the heck are you doing. DONT SPREAD IT!!!"
yeah... that would be me
This is exactly why I never liked using reduce. For loop will always produce faster results
This is why syntactic sugar is bitter sometimes.
completely agree
memcpy is also O(n), just with smaller constants
yep, there is no other way around moving 1 million stones other than moving one million stones
and if you have a shovel, you can move 5 at a time. it's still O(n)