SandCastleIcon.png This page has links to websites or programs not trusted by Scratch or hosted by Wikipedia. Remember to stay safe while using the Internet, as we can't guarantee the safety of other websites.

Efficient programming is programming in a manner that, when the program is executed, uses a low amount of overall resources pertaining to computer hardware. A program is designed by a human being, and different human beings may use different algorithms, or sequences of codes, to perform particular tasks. Some algorithms are more hefty and resource-intensive while accomplishing the same task than another algorithm. Practicing to create a low file size and low resource algorithm results in an efficient program.

Algorithm Efficiency

Time efficiency is how fast an algorithm runs in relation to input size, and space efficiency is how much memory that the algorithm consumes.[1]

Big O Notation is a function used to describe the runtime of an algorithm with the worst-case scenario. When writing in Big O Notation, only the highest term of the efficiency algorithm is used.[2] Big Theta Notation describes both upper and lower bounds of a growth rate.[3]

Generally, when using Big O Notation, it is customary to think of changing a variable as having a computational cost of "1", and setting a variable as having a computational cost of "1". List items are considered to be variables.

Here is an example script in Scratch:

repeat (n)
  set [x v] to ((x) + (1))
end

In this script, the input is n.

This script goes through a loop n times. Due to how loops are run, each loop through generates a computational cost of 1. This happens n times, so the loop has a computation cost of n. Each loop through, the script also reads and sets x, which is a computation cost of 2. Since this repeats n times, this is a computation cost of 2n. The overall efficiency of this algorithm is n + 2n = 3n, or in Big O Notation, O(n). The 3 is discarded for simplicity.

change [x v] by (n)

This code accomplishes the same task, but only one variable assignment is executed, no matter what the value of n is. Its efficiency is O(1), or constant time. Therefore, this code is more efficient than the previous one.

Computation difficulty is important in Scratch because using algorithms with a lower Big O Notation can often lead to speed improvements in projects that lag a lot.

Gaming Efficiency

Roller Coaster Tycoon is highly praised for being one of the most efficiently-programmed games. It was coded by Chris Sawyer in the 1990s and worked on some of the oldest machines of that time. It still runs very well on the newest hardware and operating systems.

Gaming is one of the highest-earning markets in the computer and video game console world. Efficiency in gaming machines varies but similar patterns have been seen over the years. In the 1990s during the dawn of what came to be modern-day gaming, computer hardware was much inferior to its current state. Programmers typically had to focus very much on efficiently programming their games so they could run on the hardware. However, hardware's' overall power has increased exponentially throughout the new millennium, and the general need to focus on efficiency has decreased.

Console games are typically programmed more efficiently than PC games because the game are designed and optimized to run on one particular type of machine. On PCs, games must be programmed to work on thousands of hardware combinations. Very often console-coded games are ported over to PCs and therefore run less efficiently. Games that run less efficiently are optimized, and do not use the minimal amount of resources. It is important for many games to be efficient, this would allow machines to run the game at the most optimal speed, giving the user the best experiance.

Efficiency Over the Years

True efficiency of a particular program is subject to argument, as programs certainly do become more resource-intensive throughout time as computers' power is put to the task of operating heavier data calculations. However, processing power can also be abused and result in a program that is programmed inefficiently. Efficiency varies from program to program, but is often taken into consideration still so a program can run better on an older machine.

In Scratch

In Scratch, optimization is important for larger projects because Scratch is an interpreted language. Compiled machine code that runs on the computer reads other codes or "interprets" them which causes Scratch to be resource-intensive. 3D projects, for example, run at a poor frame rate typically in Scratch because Scratch is not efficient enough or optimized for 3D. Furthermore, in Scratch most of the rendering is done by the processor, which makes it even more CPU-intense. Efficient programming also allows you to have more content or a smaller file size in a Scratch project, because the scripts would take up less space, letting you make more use out of 50 MB.

Similar Scripts

One common problem that makes projects slow is the use of multiple very similar scripts. Take the following, for example:

when gf clicked
forever
if <key [right arrow v] pressed?> then
change x by (10)
end

when gf clicked
forever
if <key [left arrow v] pressed?> then
change x by (-10)
end

Rather than using two scripts, it would be much better and faster to combine them into one:

when gf clicked
forever
if <key [right arrow v] pressed?> then
change x by (10)
end
if <key [left arrow v] pressed?> then
change x by (-10)
end

Graphic Effects

Another common issue that causes Scratch projects to slow down is the use of Graphic Effects. The removal of Pixel Bender support in the flash player makes these blocks very slow.[4] The effects blocks slow down scripts the most when they are placed in a loop (repeat, forever, etc.) This script, for example, would cause a project to lag:

when gf clicked
forever
change [color v] effect by (10)
end

The exceptions to this are the "ghost" and "brightness" effects. While they may slow things down a little bit, it won't lag nearly as much as the other effects, because the "ghost" and "brightness" effects did not go through Pixel Bender.

The use of Custom Blocks is another factor that can slow down a project immensely. This happens especially when there's long scripts running without screen refresh.

Repeated Computation

For complex projects, an issue that can cause Scratch projects to slow down is the repeated recalculation of a value. Instead of computing a value multiple times, it is helpful to store the value in a variable and use the variable instead. For example, this script is inefficient:

when gf clicked
forever
  change x by ([cos v] of (30))
  if <touching [edge v]?> then
    change x by ((0) - ([cos v] of (30))
  end

This script is efficient:

when gf clicked
forever
  set [cos v] to ([cos v] of (30))
  change x by (cos)
  if <touching [edge v]?> then
    change x by ((0) - (cos))
  end

Values include not just math equations, but also sensing blocks.

References

  1. http://jcsites.juniata.edu/faculty/kruse/cs2/ch12a.htm
  2. http://cs.bluecc.edu/java/CS260/Notes/Efficiency.htm
  3. http://stackoverflow.com/questions/3230122/big-oh-vs-big-theta
  4. http://scratch.mit.edu/discuss/topic/32172/