Things I learnt during my latest Javascript Code Kata

Sometimes I do a code kata at codewars.com. That is a fun way to solve computer science related problems, learn on the way to solve them and especially learn from the solutions of others.

Today I completed the kata “Make a spanning tree” using Javascript. I occasionally use Javascript to write an event handler or so but I don’t have much experience in “modern” Javascript. Here is what I learnt from looking at the solutions of others.

Destructuring

I know this from my Scala class and Clojure.

You can assign array elements to variables:

so “…rest” is assign the rest of the array.

This is nice syntactic sugar also when working with nested arrays. Eg when “edges” is an array of pairs:

There is object destructuring:

and even assigning to new variable names

See MDN web docs for more.

Spread operator to create an array using an array literal

Using an array literal to create an array from two other arrays:

Objects are associative arrays (aka Maps)

Although I already knew this, kind of, this refreshes my JS
knowledge.

First, you can add properties to Objects without declaring them in
the first place:

Second, instead of the dot-notation you can use array index
notation using the property name as the index:

One solution uses this in order to save the weighted edges in an
object just like i did in the proper Map object:

Third, methods are kind of properties, too. In the same solution,
“minOrMaxFunc” is cleverly choosen (“minOrMax” argument is either
“min” or “max”):

it creates an objects with two methods: “min” and “max” and then
accesses the one that is given in the argument. If “minOrMax” is
“min”, a reference of the “min” method is returned.

Strings are arrays

Destructuring works with strings:

and you can index strings:

“var” vs. “let”

Of course, the solutions written in “modern” JS use “let” and
“const” all over the place. I just reassured myself about the
difference between let and var:

First, variables declared in a block using “var” are visible
outside that block and are “known” before being declared:

a block might be a for-loop.

Variables declared using let are not visible outside the block and
are not “known” before declared:

Third, you might not redeclare a variable using let:

So basically, “let” is a sane way to declare variables.

Also on:

When in doubt, refactor at the bottom

When in doubt, refactor at the bottom by Eric NormandEric Normand (The Practical Dev)
But every ten-line bit of repeated code has nine two-line bits and eight three-line bits. There's probably something there to extract. Start there, with smaller abstractions. Start refactoring at the bottom!

I like Eric Normand’s idea: when in doubt, refactor few lines of code rather than more lines. Extract 2 or 3 lines and give them a name (method or function). I am aware he usually uses Clojure where you often see short functions. But it applies to other programming languages as well.

How to Benchmark Alternative SQL Queries to Find the Fastest Query

How to Benchmark Alternative SQL Queries to Find the Fastest Query (Java, SQL and jOOQ.)
Tuning SQL isn’t always easy, and it takes a lot of practice to recognise how any given query can be optimised. One of the most important slides of my SQL training is the one summarising "how to be fast"

Lukas Eder from JOOQL posts some code to benchmark SQL statement. Comes in flavours of PostgreSQL, Oracle and SQL-Server. Handy.

Parallel Stream Processing with Java 8 Stream API

Brian Goetz, Java Language Architect at Oracle, gave an interesting presentation “From Concurrent to Parallel” (available on InfoQ) on the subject back in 2009. Here are the most important points of his talk.

Java 8 introduces the Stream library (which was, in Brians words, developed as a showcase for the new Java 8 language features). Just calling “.parallel()” advices the library to process the stream “in parallel”, i.e. in multiple threads.

Do you really need it?

Parallel processing is an optimization and therefore the general questions regarding optimizations have to be answered:

  • Do you have any performance requirements at all (otherwise you are already fast enough)
  • Do you have any means to measure the performance?
  • Does the performance you measure violate the requirements?

Only if the answer to all these questions is “yes” you may take the time to investigate whether “.parallel()” will increase the performance.

Why the performance may not increase?

Compared to sequentionally processing a stream, processing it in parallel has overhead costs: splitting the data, managing the threads that will process the data and combining the results. So you may not see as much speed up as you might hope for.

Brian talks about several factors that undermine speedup.

NQ is insufficiently high

He talks about a simple model called “NQ model”. N*Q should be greater than 10.000. N is the number of data items. Q is factor that expresses how CPU-expensive the processing step is. “Summing numbers” or “finding the max of integers” is very inexpensive and Q would be near 1. More complex tasks would have higher values of Q. So if all you want is to add up numbers, you need a lot of numbers to see a performance gain.

Cache-miss ratio too high

If the data to be processed is saved next to each other in RAM, it will be transfered together in CPU caches. Accessing cache memory instead of main memory is very fast, so data in an array is processed much faster than data in a linked list that is spread all over the main memory. Also when the data in an array is just pointers data access will be slow. As a demonstration, Brian shows that summing up an array of (native) integers in parallel scales well with number of CPU cores. Summing up an array of Integer-objects scales very poorly because there are just pointers in the array.

The more indirections (pointers) you work with the more cache-misses will have the CPU wait for memory access.

The source is expensive to split

In order to process data in parallel, the source of the data has to be splitted in order to hand parts of the data to different CPUs. Splitting arrays is simple, splitting linked list is hard (Brian said: linked list are splitted into “first element, rest”).

Result combination cost is to high

When the result combination is the sum of numbers, that is easy to calculate. If the result is a set, and the result combination is to merge the resulting sets, this is expensive. It might be faster to sequentially add each result into one set.

Order-sensitive operations

Operations like “limit()”, “skip()” and “findFirst()” depend on the order of the data in the stream. This makes the pipelines using them “less exploitable” regarding parallelism. You can call “unordered()” if the order is not meaningful to you and the JVM will optimize those operations.

Mutating shared state is a big NO!

Of course you will lose performance if you have to mutate shared state and guarding access to it with locks etc.

Parallel streams are for CPU-heavy process steps

Brian mentions that parallel streams where built for CPU-heavy tasks. If you do mainly IO in the processing steps than use ThreadPools and Executors etc.

What degree of parallelism does the Stream API uses?

As stated in the Streams API documentation, the API uses one JVM wide Fork-Join-Pool with a number of threads that defaults to the number of processors on the computer system. Why? Because it is expected that a processing steps will utilize the CPU as much as possible. So there is no sense in having more threads then CPU cores.

In contrast, when having IO-heavy tasks you want to have many more threads than CPU cores because the threads will wait for IO most of the time and therefore not utilize the CPU.

Also on:

A “synchronized method” bug

In Java, a synchronized method is not thread safe if it reads from and writes to one or more static member variables.

Consider:

and assume the access to someCounter is somehow thread safe because of the synchronized keyword on doSomething.
As soon as you call doSomething concurrently on multiple SomeClass instances, it will not print unique numbers. This is because the all instance share the same static member variables. Between the increment of someCounter and printing it, its value might have already changed by another instance.

That particular bug was a bit hidden because a “SomeClass” instance was “cached” in a JEE stateless session bean. Of course the JEE container creates multiple instances of the session bean and hence multiple instances of SomeClass.