Loop unrolling is code optimization technique that reduces loop iteration count by inlining a repeated (usually a power of 2 times) sequence of loop body statements. It can be done either manually or by the compiler. At the very minimum, loop unrolling tries to improve the performance by reducing the number of loop condition checks and loop cycles (CPU jumps). Besides that, it can provide further optimization opportunities. Especially when done manually, as it can allow the programmer to consider various tradeoffs.

In this blog post we will analyse one such example, by unrolling a loop of string search algorithm…

The core of Aho-Corasic search algorithm

In my previous blog post I’ve presented the implementations of three string search algorithms: Knuth-Morris-Pratt, Shifting Bit Mask (known in the industry as Bitap / Shift-or / Shift-and / Baeza-Yates–Gonnet) and Aho-Corasic. Before running any benchmarks, I was expecting Aho-Corasic to be the fastest one, but I was wrong: it turned out to be slower than the other two! This time, I decided to do something about it, and set out to improve the performance of this algorithm. And it did not look like an easy challenge! …

Software engineering can be full of surprises, especially when it comes to performance. For example, what happens if we try to run this innocent looking Java code?

// String.repeat requires JDK 11 or above:
final var needle = "A".repeat(500000) + "B";
final var haystack = "A".repeat(1000000) + "B";
System.out.println(haystack.indexOf(needle));

We wait, and wait, and wait… At least on my 2015 year model laptop, with OpenJDK 13, it takes around a minute to find this particular needle in the haystack. This is the good old JVM, with decades of performance improvements, and efficient intrinsic implementation of String.indexOf, so what is going…

A new release of Scala programming language, 2.13, has been announced recently. It is time to look at what improvements it has brought to us. In this post I will focus on the changes in the standard library, so this can be considered a follow up to my previous post, The little gems of Scala standard library. Many of the features described here are not mentioned in the official release notes (where you can find a broad description of general language, collection and compiler improvements).

1. scala.util.Using

This finally gives us an implementation of “Loan” pattern, allowing safe and automatic closing of…

Scala programming language has a really rich standard library, especially when it comes to collection related functionality. There are many features that are often overlooked, but if applied, can greatly simplify your code. In this post I will try to introduce some of the lesser known, but really useful methods, with the goal of writing cleaner, more robust and efficient code.

Let’s start by building ourselves a small sequence of integers for experimenting:

val xs = Seq(4, 5, 2, -1, -3, 4)

It will be used in most of the examples in this post. You can try all of the…

In my previous blog post, we delved under the hood of Scala for-comprehension. This time, we’ll take a similar approach and will become familiar with another great feature of this powerful programming language — pattern matching. Again, we’ll be doing it in a series of small steps, by writing some short snippets of code.

We begin by declaring a very simple case class that we will soon dissect:

case class FullName(first: String, last: String)

Among many other useful features of case class (such as structural equals, hashCode, copy and toString), Scala compiler provides support for the following code, which constructs…

If you are the kind of person who likes to check what’s under the hood of things, and happen to be in the process of learning the Scala programming language, this post is precisely for you. In a few short steps, we will take one of the most powerful constructs of Scala — the for-comprehension, figure out what is under the hood of it, and hopefully discover some rules that would help make our code easier to follow.

Let’s start by defining a simple class hierarchy that we will be using. If you are already somewhat familiar with Scala, you’ll…

Us, humanity, have for centuries believed that we are the smartest thing on Earth. No other creature or mechanism could even approach our intellectual abilities. Recently, however, things started to change:

  • first, there was a defeat in 1997 of world chess champion Garry Kasparov by Deep Blue chess program
  • board game Go (considered one of the most complex games) held until 2016, when Go grandmaster Lee Sedol was defeated by AlphaGo program
  • 2017 — professional poker players dominated by Artificial Intelligence
  • 2018 — Dota 2 video game veterans steamrolled by AI team
  • soon, AI may make the steering wheels and…

Linas Medžiūnas

Software engineer at Chronosphere.io; unretired competitive programmer; 2x IOI gold medal winner; curious about Quantum algorithms.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store