Clicky

Gantt chart with D3.js

Apr 9, 2017

At work I’ve had a task to implement a Gantt chart diagram to show dependencies and order of some… let’s say, milestones. Given this feature is in a very unstable beta in Google Charts, I thought to myself: “Why don’t I implement it on my own?”. And tried to recall my D3 knowledge.

I’ve also found a minimalistic, but helpful example / screenshot of some Gantt chart implementation:

Challenges here were:

  1. order milestones on a timeline
  2. scale milestones to fit in a viewport
  3. create pretty connection lines
  4. center text inside each milestone

And since D3 is a data-driven library, I was using map/reduce everywhere.

And here’s the result:

The code is under the cut.

My new hobby

Apr 9, 2017

I’ve got amused by how deep and well-designed are those old ASCII-art rogue-like games! So for the last couple of days I’ve spent enomerous hours playing as a Necromancer Troll (Beat enemies! Eat enemies!) in ADOM and taking command of a dwarwish horde in Dwarf Fortress. Amazing level of detail! Most powerfull graphics engine in the world (which is your own imagination)!

Entanglement

Mar 13, 2017

Entanglement?

Some time ago there was a game popular over there, called Entanglement:

There are a few implementations of this game under Android:

But there was no such game for iOS. And as I pursued my second M. Sc. degree, I have had a course “iOS development”, where we were learning to use Swift and iOS platform.

As a course project I decided to implement this game. In Swift. Originally the game was implemented in Swift 2 (there was no Swift 3 back those days).

And recently I decided to refactor the game a bit and update it to the most recent Swift version (which is Swift 3 by the moment of writing this post).

In this post I’ll describe some interesting decisions I made while creating this game.

libc.js: component interaction

Mar 12, 2017

libc.js

Recently I’ve written a post about functional programming techniques, coming into the world of front-end and the library I crafted as an experiment. That library, libc.js was highly inspired by Elm and Mithril. But it suffered two major features:

  1. components were hardly able to be used in other components
  2. the interaction between components was nearly impossible (or, at least, not very transparent)

What’s hidden beneath the next version of the library?

Speeding-up algorithms with SSE

Feb 21, 2017

Have you ever asked anyone if assembly language might be useful nowadays? So, here’s the short answer: YES. When you know how your computer works (not a processor itself, but the whole thing - memory organization, math co-processor and others), you may optimize your code while writing it. In this short article I shall try to show you some use cases of optimizations, which you may incorporate with the usage of low-level programming.

Recently I was reading through my old posts and found out there is a gap in the article about SSE - the post did not cover some of the implementation caveats. I decided to fulfill this and re-publish a new version.

Finding maximum

So, let’s start-off searching a maximum element in the array. Usually, it is nothing just iterating through the array, comparing each element with some starting value. For optimization reason and for the precision’s sake we set the initial value to the first array’s element. Like this:

float max_value(float *a, int n) {
    float res = a[0];

    for (int i = 1; i < n; i++) {
        if (a[i] > res)
            res = a[i];
    }

    return res;
}

What we could do firstly is to store not the search element itself, but its index:

float max_index(float *a, int n) {
    int res = 0;

    for (int i = 1; i < n; i++) {
        if (a[i] > a[res])
            res = i;
    }

    return a[res];
}

This naive optimization has its effect (time in seconds; the value found in braces):

Value-based: 0.00732200 (0.99999827)
Index-based: 0.00674200 (0.99999827)

Vector operations

This is quite a universal algorithm, which could be used for any type, which allows comparing. But let’s think on how we can speed that code up. First of all, we could split array into pieces and find maximum among them.

There is a technology, allowing that. It is called SIMD - Single Instruction - Multiple Data Stream. Simply saying, it means dealing on multiple data pieces (cells, variables, elements) with the use of a single processor’ instruction. This is done in processor command extension called SSE.

Note: your processor or even operating system may not support these operations. So, before continuing reading this article, be sure to check if it does. On Unix systems you may look for mmx|sse|sse2|sse3|sse4_1|sse4_1|avx in /proc/cpuinfo file.

SSE extension has a set of vector variables to be used. These variables (on the lowest, assembly level, they are called XMM0 .. XMM7 registers) allow us for storing and processing 128 bits of data as it was a set of 16 char, 8 short, 4 float/int, 2 double or 1 128-bit int variables.

But wait! There are other versions of SSE, allowing for different registers of different size! Check this out:

SIMD extensions

MMX - hot 1997:

  • only integer items
  • vectors have length of 64 bits
  • 8 registers, namely MM0..MM7

SSE highlights:

  • only 8 registers
  • each register has size of 128 bit
  • 70 operations
  • allow for floating-point operations and vector’ elements

SSE2 features:

  • adds 8 more registers (so now we have XMM0 .. XMM15)
  • adds 144 more operations
  • makes floating-point operations more precise

SSE3 changes:

  • adds 13 more operations
  • allows for horizontal vector operations

SSE4 advantages:

  • adds 54 more operations (47 are given by SSE4.1 and 7 more come from SSE4.2)

AVX - brand new version:

  • vector size is now 256 bit
  • registers are renamed to YMMi, while XMMi are the lower 128 bits of YMMi
  • operations now have three operands - DEST, SRC1, SRC2 (DEST = SRC1 op SRC2)

SSE operations

So, I mentioned horizontal vector operations. But let’s do it in a series.

There are two SSE operation types: scalar and packed. Scalar operations use only the lowest elements of vectors. Packed operations deal with each element of vectors given. Look at the images below and you shall see the difference:

Horizontal operations deal on vectors in a different direction. Instead of operating on elements in the corresponding positions, these operate on elements in adjacent positions:

Functional web

Feb 18, 2017

In last couple of years the functional programming paradigm became very popular. A huge amount of libraries, tools, tutorials and blog posts appeared. Although the paradigm itself is rather old (lambda calculus was developed around 1930 and the Lisp language was introduced in 1950), its popularity blowed up rapidly somewhere in 2014-2016 and that’s what is happening right now. Probably one of the most powerfull influencers, giving FP (functional programming) that thrust is web development. Since Facebook introduced React, the community started incorporating many things from FP with React - including Redux and Immutable.js. But there are much more interesting things which were invented on this wave of FP popularity. One of them is Elm.

This is a story how I implemented invented yet another web framework wheel.

Clojure guards

Dec 21, 2016

Once I wanted to have something like a pretty “match” operator from Scala, but in Clojure. And hence there are no default options for it in Clojure out of the box, here are some alternatives I’ve found in the Internet.

Big O notation

Aug 25, 2016

The best big O notation explanation I’ve ever saw I’ve found on… Google Play Market! I was hanging around, looking for the suggested software and, for some reason, I’ve decided to install some educational application for programmers. And here’s what I’ve found…

Writing fast and beautiful code with C++ and D

Mar 22, 2016

Introduction

Currently I am writing my (second) master’s thesis. And it’s one of the hardest work I’ve been doing ever. It’s about image and video processing. And I’m using OpenCV.

Using OpenCV is an interesting decision: if you want to create a beautiful OO architecture for your program, you’d rather use something like Java. But I didn’t manage to run OpenCV in Java =P

So I decided to write my code in C++. Yeah, tough decision… After spending some time implementing that, I understood why it was not the best decision: my solution was too heavy (435 LOC) and it didn’t even contained four major method’ implementations!

Then I sit back and thought: “Couldn’t I use C++ for video/image reading only? And write the rest of the code in a more OOP-friendly language?”. And that’s when I started looking for a language with nice syntax and OOP features (like interfaces, short array syntax, tuples/maps, etc.) and found D language.

I’ve been looking at D a very long time ago, but had never actually tried it for writing anything more complex than a “Hello, World!” program. “That’s my star time!” - I thought.

My idea was to:

  1. create small C++ library for video IO
  2. create D program, which processes video, read using that C++ library

D offeres nice C++ interop, except it requires you to define classes/functions signatures you are importing from C++. That was not a big deal for me since I had no complex classes written yet.

Chicken in Blender

Mar 5, 2016

This is a chicken. This 3D model I’ve made in 3.5 hrs in Blender (with texturing).

Taking into account the fact I’ve started learning Unity 3D, I will possibly use this in the remake of my old Shoot Them! game. Like this (early preview, made with Unity 3D in ~3 hrs):