Programming Optimization

[LtStaffel]

Hello,

 

The Situation < >

I am trying to optimize JavaScript scripts right now, I need them to take as little time to run (or the fastest execution times) possible.

My question is not language specific though, regardless of the fact I am currently dealing with JavaScript.

</ >

 

What I think I know < >

That a compiled program with less assembly instructions runs faster than one that has more instructions for the computer to do.

That scripts are compiled on the fly and then executed without the binary being outputted unless otherwise specified.

</ >

 

What I don't know < >

If a script can be optimized.

If it's possible, how to optimize a script.

</ >

 

TLDR / QUESTION < >

How can I optimize my scripts?

</ >

 

Thanks in advance!

-LtStaffel

[tp95112]

Are you familiar with Big O notation?

[LtStaffel]

2 minutes ago, tp95112 said:

Are you familiar with Big O notation?

Negative

[SCHISCHKA]

javascript is kinda lanuage specific coz its a script. look up google tech talks on the subjet

[tp95112]

1 minute ago, LtStaffel said:

Negative

Some googling and youtubing will give you some insight on time complexity of a program. Its alot more theory but could give teach you something when coding.

Here's a little site that should give you some idea of what it is.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

But as for optimizing that comes to your ability to have less calculations and stuff

[LtStaffel]

1 minute ago, Erik Sieghart said:

Don't use Javascript?

But optimizing usually involves refining your algorithms.

Web browsers and this project I'm doing are JS only

[SCHISCHKA]

7 minutes ago, Erik Sieghart said:

You can't compile JavaScript.

kind of. you can compile from javascript to javascript. Theres also something special google's browser does but I have not had time to look into it.

https://developers.google.com/closure/compiler/

 

[Nineshadow]

While optimizing programs at an assembly level does bring some performance improvements, it's nothing compared to the complexity of the algorithm you are using. That's what will make the most impact.

Imagine an algorithm in which you're taking into consideration all combinations of a set. That will have a complexity of O(2ⁿ). Things are fine until you get to tests with values of n up to, let's say 30. But after that? What if n is 100? The program would not finish in our lifetime. No matter what low-level optimizations you make, it will still take a tremendous amount of time

[Cruorzy]

You can always minify it afterwards (removing all the spaces,comments,enters) and take a handful of scripts and let them concat and make 1 script of it all.

This is to save script file sizes and making 1 script is actually faster than calling a few scripts when loading the webpage.

[mathijs727]

Find a (line) profiler for Javascript and profile your application.

Optimize pieces of code from most expensive to least expensive.

According to the (CS master) course Optimization and Vectorization, the checklist you should follow is:

1. Profile to determine hotspots
2. Analyze the scalability of the hotspots
3. Apply high-level optimizations (algorithmic improvements)
4. Profile again
5. Parallize
6. Use GPGPU
7. Profile again
8. Apply low level optimizations (use floats instead of doubles, prevent casts, take computations out of loops if they dont rely on loop variables, early out loops, use SSE/AVX, etc...)
9. Repeat steps 7 and 8 untill time runs out

 

If you are interested in the slides of the optimization course, they are available online, google "uu optimization and vectorization"

[FreeGeekLucas]

On 2017-02-23 at 6:49 PM, SCHISCHKA said:

kind of. you can compile from javascript to javascript. Theres also something special google's browser does but I have not had time to look into it.

https://developers.google.com/closure/compiler/

 

They're related but distinct. What you're referring to tends to be called transpilation.

[DeadlyGrnSpirit]

On 2/23/2017 at 8:02 PM, LtStaffel said:

What I think I know < >

That a compiled program with less assembly instructions runs faster than one that has more instructions for the computer to do.

That scripts are compiled on the fly and then executed without the binary being outputted unless otherwise specified.

</ >

 

As a general rule this is how optimization should be thought of as. Not even specific to any language, you want to be executing as few instructions as possible. It can be damn near impossible to optimize certain things. For example:

int i = 4;

cannot be further simplified. This, however, could be.

int i = 2;
i++;
i++;

The result is the same, the amount of instructions required is not.

This is where scripts specifically might come into play. Some compilers may see the code above and automatically optimize it to something like the first example. However, scripts don't have the luxury of being precompiled before being run, so they dont benefit from this. Obviously this is a simplistic example, but try finding instances in your code where you might take multiple instructions to get the same result as one.

 

EDIT:

 

Just one way you could try doing this I thought of...

Try avoiding multiple function calls if you can do it in one. This may seem minor, but in situations of mass repetition (like in a loop) this could help. I'm not an expert on Javascript, but I know this to be the case in other languages. Obviously still make your functions do their job, but be conscious of how many calls you make and try to think of clever ways to reduce them.

Edited February 26, 2017 by DeadlyGrnSpirit

[Mira Yurizaki]

I would argue against trying to find all the ways you can optimize. Just find ways you can refine your algorithm and functions, but don't start trying to hand tweak them for the best possible outcome. I say this because any decent interpreter/compiler/assembler these days should do that for you. It's also better to have readable code that takes a smidgen longer to run.

 

I mean, unless you're working on really tight constraints, there's no reason to save a few clock cycles of work if it's going to take a tremendous amount of effort.

[DeadlyGrnSpirit]

34 minutes ago, M.Yurizaki said:

I would argue against trying to find all the ways you can optimize. Just find ways you can refine your algorithm and functions, but don't start trying to hand tweak them for the best possible outcome. I say this because any decent interpreter/compiler/assembler these days should do that for you. It's also better to have readable code that takes a smidgen longer to run.

 

I mean, unless you're working on really tight constraints, there's no reason to save a few clock cycles of work if it's going to take a tremendous amount of effort.

As a general rule I would agree, but in the context of optimization I assume every instruction counts. Most programs will never need to be optimized. They can just run and be fine. But some cases it's really important to optimize them, (ie sorting algorithms), and readability should take a hit. Your code should be documented anyways, so you can probably find a way to make sense of the code with comments.

[Mira Yurizaki]

Just now, DeadlyGrnSpirit said:

As a general rule I would agree, but in the context of optimization I assume every instruction counts. Most programs will never need to be optimized. They can just run and be fine. But some cases it's really important to optimize them, (ie sorting algorithms), and readability should take a hit. Your code should be documented anyways, so you can probably find a way to make sense of the code with comments.

If it's a commonly used algorithm, like sorting algorithms, you should be finding libraries that already implements them. Hopefully by someone who's optimized them to hell already that they can't squeeze anything else out of the compiler.

 

I would also argue that hand-tuning optimizations are more of an exercise in academics than practicality unless you're doing something that really should be high performance, like writing kernel code.

[DeadlyGrnSpirit]

2 minutes ago, M.Yurizaki said:

If it's a commonly used algorithm, like sorting algorithms, you should be finding libraries that already implements them. Hopefully by someone who's optimized them to hell already that they can't squeeze anything else out of the compiler.

 

I would also argue that hand-tuning optimizations are more of an exercise in academics than practicality unless you're doing something that really should be high performance, like writing kernel code.

The general message im trying to give is avoid unnecessary function calls, im not getting down to like the assembly level

[Mira Yurizaki]

2 minutes ago, DeadlyGrnSpirit said:

The general message im trying to give is avoid unnecessary function calls, im not getting down to like the assembly level

I would rather call a half dozen functions from a library that runs like a well oiled machine than attempt to in-line write it myself and fail miserably.

 

Besides, depending on the compiler/interpreter/whatever, it may just in-line insert them anyway if it figures out there's no other dependencies or whatnot.

 

The point is, don't try to outsmart something people with way more years of experience have already probably figured out.

[Unimportant]

I'm not familiar with how javascript is actually executed on a machine level (interpreted, dynamic recompilation, ... ?) but as a general rule, one should take great care when relying on this "big O" notation. What you think is slow or fast and what actually is fast or slow can differ greatly on a real machine.

 

Modern PC's rely greatly on cache, and because of that greatly dislike indirection. In many cases that totally breaks the "big O" notation.

As an example, inserting something at a random position should be vastly faster in a linked list then in a normal linear array, according to big O. After all, in a linked list you can simply insert a node while in a array you'd have to move all the elements behind the insertion point 1 position, and that seems expensive.

 

In reality, the linear array approach will totally destroy the linked list, we're talking orders of magnitude here, no contest.

Since the nodes in the linked list are scattered in memory, each hop to a new node is almost surely a cache miss. Cache misses are so expensive that the linear array has moved it's elements by the time you've hardly started traversing the linked list looking for your node.

 

The moral of the story: Always measure and benchmark. You can use theoretical models to try and device new ways of doing things but never forget to actually test. The results might confound you. Try to be compact and local, so the cache controller likes you, that does far more then clever algorithms.

[LtStaffel]

2 hours ago, M.Yurizaki said:

I would argue against trying to find all the ways you can optimize. Just find ways you can refine your algorithm and functions, but don't start trying to hand tweak them for the best possible outcome. I say this because any decent interpreter/compiler/assembler these days should do that for you. It's also better to have readable code that takes a smidgen longer to run.

 

I mean, unless you're working on really tight constraints, there's no reason to save a few clock cycles of work if it's going to take a tremendous amount of effort.

Take a peek at "hackmud" on Steam.

 

My scripts to be their absolute fastest to get the very best results. For instance, a script a lot of people have there is a "scraper" to look for the real world equivalent of IP Address of other players in order to hack them. The difference between 400ms faster or slower is the difference between finding that IP of the big player with lots of points and hacking him before someone else does, since our scripts only get run for 5 seconds no matter where they are in their operations when that 5 seconds is up.

 

Thank you for the information in your other posts too!

[Mira Yurizaki]

3 hours ago, LtStaffel said:

Take a peek at "hackmud" on Steam.

 

My scripts to be their absolute fastest to get the very best results. For instance, a script a lot of people have there is a "scraper" to look for the real world equivalent of IP Address of other players in order to hack them. The difference between 400ms faster or slower is the difference between finding that IP of the big player with lots of points and hacking him before someone else does, since our scripts only get run for 5 seconds no matter where they are in their operations when that 5 seconds is up.

 

Thank you for the information in your other posts too!

400ms on a local level means your algorithm design needs work. If you're down to chopping of handfuls of clock cycles or instructions where you're saving nanoseconds, the indeterminate nature of networks makes any tiny optimization, at least in my eyes, not really worth the effort.

[LtStaffel]

7 minutes ago, M.Yurizaki said:

400ms on a local level means your algorithm design needs work. If you're down to chopping of handfuls of clock cycles or instructions where you're saving nanoseconds, the indeterminate nature of networks makes any tiny optimization, at least in my eyes, not really worth the effort.

The script gets to run for 5 seconds in total. I upload it to the game server and it runs there so it can run in strict mode (no eval() and such). It has to brute force 4 digit pins, it has to identify Base64 strings, it has to locate those in-game IPs and store them to a Mongo DB, and it does not stop running, it just finds things and keeps going. If I can make it find 80 user IPs in 5 seconds vs my enemy's who can find 100 user IPs in 5 seconds, then the optimization makes a massive difference. When the 5 seconds is up, the game server stops the script, and it will have to be run again to continue.

 

Beyond all this, is I am trying to learn a bit about more realistic code applications. I will remember that optimizations at this level make little to no difference in a real world setting. It is just this game that really really needs every ms it can get out of each script.

[Mira Yurizaki]

16 minutes ago, LtStaffel said:

The script gets to run for 5 seconds in total. I upload it to the game server and it runs there so it can run in strict mode (no eval() and such).

These sorts of details would be nice to know beforehand.

Quote

It has to brute force 4 digit pins, it has to identify Base64 strings, it has to locate those in-game IPs and store them to a Mongo DB, and it does not stop running, it just finds things and keeps going. If I can make it find 80 user IPs in 5 seconds vs my enemy's who can find 100 user IPs in 5 seconds, then the optimization makes a massive difference.

All you can really do is choose the best algorithm for the job, implement it as cleanly as possible, then hope for the best. Avoid anything that requires waiting or dependencies.

 

While function calling has a penalty, a mature compiler should figure out if the function can be in-lined into the code or not.

 

Also I found out that, at least with Firefox's JavaScript engine, somehow it's better to do a function call than it is to do what was in the function. I made this function:

var doStuff = function(){
  for(var i = 0; i < 10000; i++){
   i = i;
  }
}

Then in Firefox, this is what happened:

var start = performance.now(); doStuff(); console.log(performance.now() - start)
0.06999999999970896 
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
0.055000000007566996 
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
0.059999999997671694 
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
0.059999999997671694 
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
0.059999999997671694 
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
0.055000000007566996 
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
0.06000000001222361 
undefined

However, when I simply did the contents of the function, I got a much different result:

var start = performance.now();   for(var i = 0; i < 10000; i++){
   i = i;
  }; console.log(performance.now() - start)
11.990000000005239 
undefined
var start = performance.now();   for(var i = 0; i < 10000; i++){
   i = i;
  }; console.log(performance.now() - start)
10.254999999990105 
undefined
var start = performance.now();   for(var i = 0; i < 10000; i++){
   i = i;
  }; console.log(performance.now() - start)
9.904999999998836 
undefined
var start = performance.now();   for(var i = 0; i < 10000; i++){
   i = i;
  }; console.log(performance.now() - start)
9.535000000003492 
undefined

And just to be certain, I ran it on Chrome, which has one of the fastest JavaScript engines available:

var start = performance.now(); doStuff(); console.log(performance.now() - start)
VM70:1 0.0750000000007276
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
VM72:1 0.029999999998835847
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
VM74:1 0.08499999999912689
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
VM76:1 0.014999999999417923
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
VM78:1 0.010000000002037268
undefined
var start = performance.now(); doStuff(); console.log(performance.now() - start)
VM80:1 0.010000000002037268

And then what happens if I did the contents of the function?

var start = performance.now();   for(var i = 0; i < 10000; i++){
   i = i;
  }; console.log(performance.now() - start)
VM82:3 0.3100000000013097
undefined
var start = performance.now();   for(var i = 0; i < 10000; i++){
   i = i;
  }; console.log(performance.now() - start)
VM83:3 0.12999999999738066
undefined
var start = performance.now();   for(var i = 0; i < 10000; i++){
   i = i;
  }; console.log(performance.now() - start)
VM84:3 0.125
undefined
var start = performance.now();   for(var i = 0; i < 10000; i++){
   i = i;
  }; console.log(performance.now() - start)
VM85:3 0.13999999999941792
undefined
var start = performance.now();   for(var i = 0; i < 10000; i++){
   i = i;
  }; console.log(performance.now() - start)
VM86:3 0.24499999999898137

And just to make sure this wasn't a coincidence, I ran it on Edge. Similar result: calling a function is an order of magnitude faster than doing the function's contents in-line.

 

What I'm trying to say is unless you're willing to get intimate with your JavaScript engine's quirks and profile how it handles things, your only option is to do a lean as possible implementation.

 

Also don't try to redefine anything JavaScript already provides. Chances are if it's a utility function, it's already well optimized.

[LtStaffel]

2 hours ago, M.Yurizaki said:

These sorts of details would be nice to know beforehand.

 

All you can really do is choose the best algorithm for the job, implement it as cleanly as possible, then hope for the best. Avoid anything that requires waiting or dependencies.

 

While function calling has a penalty, a mature compiler should figure out if the function can be in-lined into the code or not.

 

Also I found out that, at least with Firefox's JavaScript engine, somehow it's better to do a function call than it is to do what was in the function. I made this function:

var doStuff = function(){
  for(var i = 0; i < 10000; i++){
   i = i;
  }
}

Then in Firefox, this is what happened:

However, when I simply did the contents of the function, I got a much different result:

And just to be certain, I ran it on Chrome, which has one of the fastest JavaScript engines available:

And then what happens if I did the contents of the function?

And just to make sure this wasn't a coincidence, I ran it on Edge. Similar result: calling a function is an order of magnitude faster than doing the function's contents in-line.

 

What I'm trying to say is unless you're willing to get intimate with your JavaScript engine's quirks and profile how it handles things, your only option is to do a lean as possible implementation.

 

Also don't try to redefine anything JavaScript already provides. Chances are if it's a utility function, it's already well optimized.

I did tell you in a previous post that the script only gets to run for 5 seconds. Getting optimal code for that game though is not the goal of this thread. I wanted people to tell me how to optimize my code; which they (you are one of "they") have, and I appreciate it.

 

I will play with the scripts and see what goes fastest with regards to functions and other things. The main message I'm getting from everyone though is that I should optimize my calculations as much as possible, and worry less about optimizing the code itself.

[fuzzylogic11]

On ‎2‎/‎24‎/‎2017 at 5:10 PM, Nineshadow said:

While optimizing programs at an assembly level does bring some performance improvements, it's nothing compared to the complexity of the algorithm you are using. That's what will make the most impact.

Imagine an algorithm in which you're taking into consideration all combinations of a set. That will have a complexity of O(2ⁿ). Things are fine until you get to tests with values of n up to, let's say 30. But after that? What if n is 100? The program would not finish in our lifetime. No matter what low-level optimizations you make, it will still take a tremendous amount of time

Actually you'd find that's really not so true. More often it's how you face the hardware which matters vs. the time complexity of the algorithm, at least until a fairly large N.

 

In fact linear search often beats binary search for N < 10,000.

[fuzzylogic11]

@LtStaffel, for anything involving loops, make them asynchronous. Even though JS doesn't really support multithreading, your browser CAN if you let it know the results from various calls aren't needed individually, but rather as a group. Otherwise, parallelize as much as you can server-side and have direct HTML templates for anything you're dynamically loading. If all your JS has to do is insert inner HTML, you'll find your life's much easier.