FizzBuzz

shaafiee — Tue, 26 Jan 2021 02:19:07 +0000

It’s exam day and, as soon as you wake up, your mind starts racing through all manners of algorithms, until it occurs to you that FizzBuzz was something you never attempted. You quickly fill your moka pot with water, spoon some cheap espresso grind into the filter, tighten the kettle and put it on the hob at low heat.

You flop into the only chair in your dorm room and skillfully enter your PIN on the Windows box in front of you. It takes some time for the window manager to compete with the likes of your Claymore miner to allow you to interface with your machine. As soon as the cursor on the screen synchronizes with your jiggling of the mouse (yes, the mouse), you summon Visual Studio, and start a new C++ console project.

You hastily type in a program for the typical FizzBuzz algorithm, demonstrating, to nobody in particular, the touch-typing skills that you have been honing since you were a pup. You sit back, admiring your work for two seconds, and immediately feel like challenging yourself. Leaning forward and typing furiously, you insert a high-resolution timer and change the algorithm to count (instead of displaying) the number of fizzes, buzzes and fizzbuzzes for numbers 1 through 4 billion. You end up with the following program:

#include <iostream>
#include <chrono>


int main()
{
    int fizz = 0, buzz = 0, fizzbuzz = 0;


    auto startTime = std::chrono::high_resolution_clock::now();


    for (unsigned int i = 1; i <= 4000000000; i++) {
        if (i % 3 == 0 && i % 5 == 0) {
            fizzbuzz++;
        }
        else if (i % 3 == 0) {
            fizz++;
        }
        else if (i % 5 == 0) {
            buzz++;
        }
    }


    auto endTime = std::chrono::high_resolution_clock::now();
    auto totalTime = endTime - startTime;


    printf("\t fizz : %d, buzz: %d, fizzbuzz: %d, duration %lld milliseconds\n", fizz, buzz, fizzbuzz, (totalTime / std::chrono::milliseconds(1)));


    return 0;


}

Then you turn on optimizations, compile it and run it. Before the run completes, you go over to the hob, pick up a semi-clean mug nearby and fill it with the hot black liquid from the moka pot.
You sit back down and, taking a sip from the mug, note that your algorithm took 6 seconds to complete.

Even for a machine as old as your’s (Intel i7-7700K), this feels like a long time to crunch through 4 billion numbers. So, you start optimizing your algorithm.

Being a computer science student, you note (with a mildly pompous sense of pride) that all the time is consumed by the code inside your for-loop. You recognize that for 5% (fizzbuzz) of the 4 billion numbers there are 2 modulus operations being performed, whilst for about 23% (fizz) of the iterations 3 modulus operations were performed and for the remaining iterations, 4 modulus operations were performed (not taking into account the optimizations performed by the compiler). After a flurry of keystrokes, you end up with the following modified for-loop:

    for (unsigned int i = 1; i <= 4000000000; i++) {
        if (i % 3 == 0) {
            if (i % 5 == 0) {
                fizzbuzz++;
            }
            else {
                fizz++;
            }
        }
        else if (i % 5 == 0) {
            buzz++;
        }
    }

Compile. Run! Down to 5.55 seconds.

You go through the algorithm and find yourself bemused upon realizing that each cycle of the for-loop performed exactly 2 modulus operations. That’s when you realize that the overheads of managing the for-loop and the logical operations were considerable. You start work on further optimizing your for-loop. Minutes later, you end up with the following:

    for (unsigned int i = 1; i <= 4000000000; i++) {
        isFizz = false;
        if (i % 3 == 0) {
            isFizz = true;
            fizz++;
        }
        if (i % 5 == 0) {
            if (isFizz) {
                fizz--;
                fizzbuzz++;
            }
            else {
                buzz++;
            }
        }
    }

After running the new program, you get a result of under 5.2 seconds.

Once again, your program performs only 2 modulus operations in every iteration. You realize that in the previous optimization your program performed 2 logical operations in each iteration. However, in your new optimization, your program performs 3 logical operations through 13% of the cycles and 2 logical operations each throughout the rest of the cycles. You have now established that incursions also have a cost, and you start wondering if you could limit them.

You get cracking on transforming your entire linear program into a multithreaded one. So, relying on native Windows multithreading, you fire off three CreateThread() calls, one for fizz, the other for buzz, and the last for fizzbuzz counting. This way, each thread does only 2 modulus operations with a single logic operation that does not have an incursion. Sometime after your mug is drained, you end up with the following program:

Mutithreaded Fizzbuzz

When you compile and run the program, you are thrilled to yield a computation time of 4.6 seconds. Success!

You then look at your watch and realize there was ample time to take the long way through the campus to the exam halls. Smelling your breath, and establishing that it was just south of unbearable, you pick up your bag and head outside. As you lock the door, you chuckle to yourself, “those humans don’t know what’s coming.” Then you run your tentacles through your antennae and slither off to the exam halls.

All the source

WASM: Memory Management

shaafiee — Thu, 02 Jul 2020 16:37:50 +0000

So you have chosen to write your new web app in WASM - exciting! On top of that, you want to write it in C++ to have fine-grained control over data storage and manipulation.

Here's some great advice that will help you overcome serious headaches.

Firstly, because the memory available to your program is actually a JS object, it is available as one contiguous chunk that is limited to linear scaling. This means that you have to be very careful about deleting objects and freeing memory. In fact, stop deleting objects altogether. If you feel the need to get rid of temporary memory objects then create a separate temporary memory object within JS for that operation, like so:

The second big hint is, align your data structures. When you have lots of data structures that go in and out of the execution scope, you will run into lots of segmentation faults due to memory misalignments, particularly if your structures have many levels of invariably scaling sub-structures, such as in the case of Markov chains.

No alt text provided for this image
Explicit memory alignment will have penalties in terms of growth of memory as your Markov chains' complexities increase - this is where multiple memory objects come in handy. This drawback is worth the performance and stability bonuses, which you will learn as you dig into WASM.

Have fun in your WASM journey!

Forem: shaafiee

FizzBuzz

WASM: Memory Management