tisdag 7 juni 2016

My first hashtable, part 2

Since the implementation of my first version of my hash table, I've discovered a few things:

Key Size - The implementation was really good for small keys (e.g. uint64_t), but much worse for larger ones.

Api - The "empty key" api didn't really sit well with me. Even though it was only exposed to the user in the class declaration.

So, I began reiterating my implementations, testing and benchmarking (which is a lot of fun), and after a while I came up with a result I'm quite satisfied with. Not only is the API nicer, but the performance is better; much more uniform, and in most cases faster than my previous implementation! And at ~270 lines of code, I think it's a pretty good alternative to the more common implementations out there :)

Code: https://github.com/JCash/containers

Here are some samples from the benchmarks:

söndag 27 mars 2016

My first hash table

Recently I realized I needed a hash table where I had complete control of the memory ownership.
Previously, as a placeholder, I just used a regular std::unordered_map, but now I had come to a point where it just needed to be replaced. I wanted to be able to reload my engine, while keeping the data intact in memory (Handmade Hero style).

Since I had never written one myself, I though this might be a fun exercise/challenge.
Even though the wheel is already invented, doesn't mean you can't have fun building a new one, learn something from it, or even try to improve on it. Right?

One common way to implement a hash table is to use "chaining", which means that you use a table to do the initial lookup, and then use a linked list to resolve hash collisions. Another way is to use "open addressing", where you use a "probing sequence" to find an empty slot, in case of hash collisions.

TL;DR: The code is available on GitHub

An example of the benchmarks found at the GitHub repo

måndag 28 september 2015

OSX + Parallels Desktop + Windows keyboard

I just bought a Windows keyboard to help with my coding(and gaming) but as you can imagine, not everything went without a hitch. In particular, I had troubles with the Command and Option keys due to my muscle memory of working with a mac for so long :)

Using the OSX default keymapper simply didn't work, since there you could only map Command (both) to Option and vice versa. And if you did that, the AltGr inside Parallels Desktoip Windows stopped working (and although you could map them back in Parallels Desktop, it was the same issue there, you mapped both left and right keys as one!)

The solution was to use Karabiner, formerly known as KeyRemap4MacBook. In there you could distinguish between left and right keys!

So I mapped Command Left to Options Left and vice versa, but now I had the issue of it not working in the Windows VM. Then I installed SharpKeys, which could do the same, map the keys back!

So now I have a working setup for both OS'es, and if I find a new issue, I'm pretty confident these two programs can solve that.

fredag 18 juli 2014

Install SSH server on Windows 7

Since I don't want to maintain several Parallels Desktop VM's on each of my machines (due to disc space and maintenance), I need to be able to ssh into them, but also use the same shared folder where I have my code.

Bitwise SSH Server

When googling for windows ssh servers, the majority of the answers were pretty old, but I didn't really mind that as long as they worked ok. I tried installing OpenSSH via cygwin (which was easy), but that gave me a cygwin prompt which didn't have all my user's environment variables and it also behaved erratically (and occasionally hung). I also looked into using the freeSSHD, and that had a nice UI to change settings and add users. But it just never let me log on (Access Denied), despite trying all the tricks google gave me.

In the end I limited my searches for the latest year, and at the top it suggested the Bitwise SSH Server. It's free for personal & non commercial use and it was really easy to setup. Run the installer, and then add a user in the UI settings. Et voila! Everything worked out of the box!

Shared Network Folders

The setup I have is that I have my code on my MBP, the Windows VM on an iMac. So I want to login in to the VM, and there I want to compile my code using MSVS.

Parallels Desktop is good at sharing Mac & Samba folders with the VM, but my problem is still with the ssh login: It cannot access the mapped drives!

If I run $> net use the drives are there, but I can't cd into them! They're listed as "Network: Parallels Desktop Folders" and their "status" fields are empty.

However, when I run $> net use L: \\\shared /user:MACBOOKPRO-AB12\mawe the drive mounts nicely (after password confirmation). And fortunately, the Bitwise ssh server remembers mapped shares by default (if they're mapped as Microsoft Windows Network) so the next time you log in, the drive is still there.


I've heard about the SSH server issues on windows before, but with such a great tool, I definitely think those days are gone. I am now a happy multi platform coder again!

onsdag 16 juli 2014

xxHash64 - a fast 64 bit hash function

In my work I often use various hash functions as hashes or checksums, and it's always beneficial to know about different qualities and speed of the functions available.

Yann Collet (known for the LZ4 compression algorithm) has now updated his xxHash algorithm with a 64 bit version, and it's speed is quite excellent. On my machine, a 64bit MBP @ 3GHz:
xxHash64            - ~13.5 GB/s
CityHash128         - ~12.5 GB/s
CityHash64          - ~11.5 GB/s
MurmurHash3_x64_128 - ~5.5 GB/s

The function has been tested against the smhasher suite, and passing all tests. Although the tests are more geared towards 32 bit hashes, the well known MurmurHash3 function is also tested against this suite.

The XXH64 is implemented mainly for 64 bit platforms, so it's performance is not as good on 32 bit systems. But then you probably would use XXH32 anyways.

I'm sure more tests will reveal more of the hash quality in the future.

For code and speed comparisons, check it out at https://github.com/Cyan4973/xxHash

lördag 15 februari 2014

Installing Parallels Tools on Debian 7

This entry is about remembering how I solved this issue (as well as boost some traffix for the blogger that solved it)

Parallels Tools is a package designed to make various host/guest tools work: Clipboard, shared folders etc.

For some reason though, the Parallels' way of installing it fails. And it turns out to be a mount + security problem.

First off, the iso wouldn't mount when choosing the "Virtual Machine -> Install Parallels Tools". So I had to manually find it using the "Devices -> Cd/Dvd -> Connect Image..." and browsing to "/Applications/Parallels\ Desktop.app/Contents/Resources/Tools/prl-tools-lin.iso"

But, it still wouldn't work. So, after some googling I followed this guide: Install Parallels Tools on a Debian Virtual Machine

In short these commands (on the guest) solved the issue once I got the iso mounted:

lördag 8 februari 2014

Eclipse + SSH

I work a lot across multiple systems of various OS'es and configurations, and usually I do it via ssh. However, almost everytime, the tasks get much slower than they ought to be, due to the fact that the remote system doesn't have your local tools and configs.

Since I mostly use Eclipse on my local system, and since it's plugin based, I thought of searching for such plugins, and imagine my surprise that it actually exists!

It's built in, and it's called Remote System Explorer.