The Mandelbrot-Set with Google Go (Part II)

>> Part I: The Mandelbrot-Set with Google Go (Part I)

So here’s the second part of my little field trip to Google’s new programming language “Go“.
This time I tried to use “channels” and “goroutines” to parallelize the pixel calculations across all CPU cores.

The main changes are that the parameters that are needed for the pixel calculation are now wrapped in a PointParams struct so they can easily be put into a channel.
Done that we’re instantiating 2 buffered channels so they can hold the PointParams for all pixels and the goroutines don’t block and possibly cause a deadlock.
In the next step the PointIteration() function is invoked as a goroutine. One time for each core. To do that we just have to prefix the function call with the keyword “go”. Easy, isn’t it?
Instead of directly calculating the pixels in the nested for loop we’re now just creating new PointParams and shove them into the “in” channel.
Meanwhile the running PointIteration() goroutines are fetching the PointParams from the “in” channel and when the calculation is done they’re sending a signal to the “out” channel.
All we have to do now is to wait for all calculations to finish. This is done by looping over the “out” channel and pulling all values out. The value itself does not matter so it is discarded.

As the documentation states the current implementation of the compiler does not automatically parallelize the code. Thus, if we want CPU parallelization we have to add a call to runtime.GOMAXPROCS(NCPU) in our main() function at first.

package main

import (
  "fmt"
  "os"
  "math"
  "image"
  "image/png"
  "bufio"
  "time"
  "flag"
  "runtime"
)

const NCPU = 4		// number of CPU cores

var pointX = flag.Float64("x", -2.0, "X coordinate of starting point of Mandelbrot or fix point for Julia (range: 2.0 to 2.0)")
var pointY = flag.Float64("y", -2.0, "Y coordinate of starting point of Mandelbrot or fix point for Julia (range: 2.0 to 2.0)")
var zoom = flag.Float64("z", 1.0, "Zoom level")
var julia = flag.Bool("julia", false, "Turn on Julia calculation")
var maxIter = flag.Int("maxIter", 51, "Max number of point iterations")

type PointParams struct {
  cx float64
  cy float64
  px int
  py int
}

func main() {
  runtime.GOMAXPROCS(NCPU)
  flag.Parse()

  fmt.Printf("X: %f\n", *pointX)
  fmt.Printf("Y: %f\n", *pointY)
  fmt.Printf("Zoom: %f\n", *zoom)
  fmt.Printf("Julia: %t\n", *julia)
  fmt.Printf("MaxIter: %d\n", *maxIter)

  start := time.Nanoseconds()
  img := CalculateImage(1000, 1000)
  end := time.Nanoseconds()
  fmt.Printf("Time: %d ms\n", (end - start) / 1000 / 1000) // ms
  WriteImage(img)
}

func CalculateImage(imgWidth int, imgHeight int) *image.NRGBA {
  img := image.NewNRGBA(imgWidth, imgHeight)
  minCx := -2.0
  minCy := -2.0
  if !*julia {
    minCx = *pointX
    minCy = *pointY
  }
  maxSquAbs := 4.0	// maximum square of the absolute value
  // calculate step widths
  stepX := math.Fabs(minCx - 2.0) / float64(imgWidth) / *zoom
  stepY := math.Fabs(minCy - 2.0) / float64(imgHeight) / *zoom
  cx := 0.0
  cy := 0.0

  // Create buffered in and out channels
  in := make(chan *PointParams, imgWidth*imgHeight)
  out := make(chan int, imgWidth*imgHeight)

  // start goroutine for each CPU core
  for i := 0; i < NCPU; i++ {
    go PointIteration(in, out, maxSquAbs, *maxIter, img)
  }

  for px := 0; px < imgWidth; px++ {
    cx = minCx + float64(px) * stepX

    for py := 0; py < imgHeight; py++ {
      cy = minCy + float64(py) * stepY

      // put params in channel
      in <- &PointParams {cx, cy, px, py}
    }
  }

  // drain channel and wait for all calculations to complete
  for i := 0; i < (imgWidth*imgHeight); i++ {
    <- out
  }

  return img
}

func PointIteration(in chan *PointParams, out chan int, maxSquAbs float64, maxIter int, img *image.NRGBA) {
  for {
    // get params from in channel
    pointParams := <- in

    // init vars
    squAbs := 0.0
    iter := 0
    x := 0.0
    y := 0.0
    if *julia {
      x = pointParams.cx
      y = pointParams.cy
      pointParams.cx = *pointX
      pointParams.cy = *pointY
    }

    for squAbs <= maxSquAbs && iter < maxIter {
      xt := (x * x) - (y * y) + pointParams.cx	// z2
      yt := (2.0 * x * y) + pointParams.cy		// z2
      //xt := x * (x*x - 3*y*y) + cx	// z3
      //yt := y * (3*x*x - y*y) + cy	// z3
      //xt := x * (x*x*x*x - 10*x*x*y*y + 5*y*y*y*y) + cx	// z5
      //yt := y * (5*x*x*x*x - 10*x*x*y*y + y*y*y*y) + cy	// z5
      x = xt
      y = yt
      iter++
      squAbs = (x * x) + (y * y)
    }

    color := ChooseColor(iter, maxIter)
    img.Set(pointParams.px, pointParams.py, color)

    out <- 1;	// signal that calculation is done
  }
}

func ChooseColor(iterValue int, maxIter int) *image.NRGBAColor {
  val := uint8(iterValue)
  if iterValue == maxIter {
    return &image.NRGBAColor {0, 0, 0, 255}
  }
  multi := uint8(255 / maxIter)
  return &image.NRGBAColor {0, val*multi, 0, 255}
  //return &image.NRGBAColor{^(val*5), ^(val*5), ^(val*5), 255}
}

func WriteImage(img *image.NRGBA) {
  file, err := os.Create("mandelbrot.png")
  if err != nil {
    fmt.Printf("Could not create file %s", file.Name())
  }
  writer := bufio.NewWriter(file)
  png.Encode(writer, img)
  writer.Flush()
  file.Close()
}

So far so good. But when I ran this code I was a bit irritated because it almost took twice as much time as the single threaded version.
After a while of wondering and pondering I decided to raise the max iterations so that the point calculations consume much more time compared to the default settings. And behold, it works. The parallelized version is much faster than the normal one.
With maxIter set to 40000 the single theaded version takes up to 46 seconds and the parallelized version takes about 11,5 seconds. That’s exactly the excpected ratio of 4:1. You can also see very nicely how all cores are being used.

So it seems that the overhead the channels and goroutines produce to provide thread-safety etc. is just too big when you just have fast calculations.

The produced image with that much iterations is of course pretty useless. In fact it’s entirely black due to my poor color choosing implementation.

Next up: Rust (well…maybe… :))

>> Part I: The Mandelbrot-Set with Google Go (Part I)

The Mandelbrot-Set with Google Go (Part I)

>> Part II: The Mandelbrot-Set with Google Go (Part II)

Time to learn a new programming language. This time my decision fell on a quite young member of the programming language family, namely Google Go.

The various promised features really made me a bit excited about this language, so I decided to make a simple implementation of the Mandelbrot-Set (with the option to also calculate Julia-Sets).

To keep it short – here’s the code:

package main

import (
 "fmt"
 "os"
 "math"
 "image"
 "image/png"
 "bufio"
 "time"
 "flag"
)

var pointX = flag.Float64("x", -2.0, "X coordinate of starting point of Mandelbrot or fix point for Julia (range: 2.0 to 2.0)")
var pointY = flag.Float64("y", -2.0, "Y coordinate of starting point of Mandelbrot or fix point for Julia (range: 2.0 to 2.0)")
var zoom = flag.Float64("z", 1.0, "Zoom level (only working properly for Mandelbrot)")
var julia = flag.Bool("julia", false, "Turn on Julia calculation")
var maxIter = flag.Int("maxIter", 51, "Max number of point iterations")
var imgSize = flag.Int("imgSize", 1000, "Size of the image")

func main() {
 flag.Parse()

 fmt.Printf("X: %f\n", *pointX)
 fmt.Printf("Y: %f\n", *pointY)
 fmt.Printf("Zoom: %f\n", *zoom)
 fmt.Printf("Julia: %t\n", *julia)
 fmt.Printf("MaxIter: %d\n", *maxIter)
 fmt.Printf("ImgSize: %d\n", *imgSize)

 start := time.Nanoseconds()
 img := CalculateImage(*imgSize, *imgSize)
 end := time.Nanoseconds()
 fmt.Printf("Time: %d ms\n", (end - start) / 1000 / 1000) // ms
 WriteImage(img)
}

func CalculateImage(imgWidth int, imgHeight int) *image.NRGBA {
 img := image.NewNRGBA(imgWidth, imgHeight)
 minCx := -2.0
 minCy := -2.0
 if !*julia {
 minCx = *pointX
 minCy = *pointY
 }
 maxSquAbs := 4.0 // maximum square of the absolute value
 // calculate step widths
 stepX := math.Fabs(minCx - 2.0) / float64(imgWidth) / *zoom
 stepY := math.Fabs(minCy - 2.0) / float64(imgHeight) / *zoom
 cx := 0.0
 cy := 0.0
 for px := 0; px < imgWidth; px++ {
 cx = minCx + float64(px) * stepX

 for py := 0; py < imgHeight; py++ {
 cy = minCy + float64(py) * stepY

 iterValue := PointIteration(cx, cy, maxSquAbs, *maxIter)

 color := ChooseColor(iterValue, *maxIter)
 img.Set(px, py, color)
 }
 }
 return img
}

func PointIteration(cx float64, cy float64, maxSquAbs float64, maxIter int) int {
 squAbs := 0.0
 iter := 0
 x := 0.0
 y := 0.0
 if *julia {
 x = cx
 y = cy
 cx = *pointX
 cy = *pointY
 }

 for squAbs <= maxSquAbs && iter < maxIter {
 xt := (x * x) - (y * y) + cx // z^2
 yt := (2.0 * x * y) + cy // z^2
 //xt := x * (x*x - 3*y*y) + cx // z^3
 //yt := y * (3*x*x - y*y) + cy // z^3
 //xt := x * (x*x*x*x - 10*x*x*y*y + 5*y*y*y*y) + cx // z^5
 //yt := y * (5*x*x*x*x - 10*x*x*y*y + y*y*y*y) + cy // z^5
 x = xt
 y = yt
 iter++
 squAbs = (x * x) + (y * y)
 }
 return iter;
}

func ChooseColor(iterValue int, maxIter int) *image.NRGBAColor {
 val := uint8(iterValue)
 if iterValue == maxIter {
 return &image.NRGBAColor {0, 0, 0, 255}
 }
 multi := uint8(255 / maxIter)
 return &image.NRGBAColor {0, val*multi, 0, 255}
 //return &image.NRGBAColor{^(val*multi), ^(val*multi), ^(val*multi), 255} // grey
}

func WriteImage(img *image.NRGBA) {
 file, err := os.Create("mandelbrot.png")
 if err != nil {
 fmt.Printf("Could not create file %s", file.Name())
 }
 writer := bufio.NewWriter(file)
 png.Encode(writer, img)
 writer.Flush()
 file.Close()
}

I have to admit i did not take much effort in cleaning up or optimizing the code. Mea culpa. The needed time for calculating the Mandelbrot-Set (1000×1000 px; 51 iterations) was about 600 ms on a Kubuntu VM with 2 cores@2,4GHz and 2GB RAM.

So this approach was pretty much straightforward and did a good job in getting my feet wet with Go. The next step now is to utilize some of the main features of Go: channels and goroutines for parallelization.

Finally here some pics:

>> Part II: The Mandelbrot-Set with Google Go (Part II)

Setting up a Git Server on Windows Server 2008 R2 (using msysgit and WinSSHD) [Update]

This is a follow-up post from this one. It is inspired by a comment from Dan Kendall. So thanks Dan.

In the portable version of msysgit the git-upload-pack.exe and the git-receive-pack.exe files are also located in the bin/ folder. This allows us to shrink the configuration down and even skip all configuration steps on the client.

The basic setup is the same as in the original post.

The server configuration is a bit different though.

1. Download the portable version of msysgit and extract it to C:\Git.

2. Add C:\Git\bin to the PATH variable.
(If you don’t want to use the portable msysgit for whatever reason, you also have to add C:\Git\libexec\git-core to the PATH)

3. Create a new file in C:\Git\bin and just insert

$*

Save it as shell script (.sh). E.g. “gitcmdhelper.sh”.
This basically executes the all parameters that are passed and solves the quotes-problem that is mentioned in the original post. There are surely other approaches to solve this issue and if you find a better one please do not hesitate to post a comment.

4. In WinSSHD open the advanced settings and edit the user account(s) you have set up before. Scroll down a bit and uncheck “Use group default exec request prefix”. Then change the “Exec request prefix” to

cmd.exe /c sh gitcmdhelper.sh 

Be sure to add a space at the end.

5. Done. You can connect to the server with your Git client.

git clone|push|pull|etc. ssh://username@server/path/to/myrepo 

Setting up a Git Server on Windows Server 2008 R2 (using msysgit and WinSSHD)

My first attempt to use a remote Git repository on my Windows Server was to set up a WebDAV site and connect it as network drive on my PC. In principle this works well and the setup is quite fast and easy. The only problem was that it was really slow on my Win 7 machine. Unworkable slow. Even with this magic Auto-detect proxy settings turned off it didn’t improve very much. On Win XP it worked quite well though.
So that was the one of the main reasons why I decided to set up a Git remote repo over SSH. Unfortunately there were some hurdles to take to get this to work.

Basic Setup:

1. Go download and install WinSSHD on your Server. There’s a free version for personal use.

2. Configure WinSSHD. Set up the account(s) you want to use etc. This should be pretty straightforward, as it’s all self-explaining.

3. Now you should be able to connect from a remote client using simple password authentication. For example in Git Bash you can try to connect by typing

ssh username@server

If the connection works. Type ‘exit’ to disconnect and return to the bash

4. Since we don’t want to use password auth the next step is to generate a ssh key pair.
(You can configure the allowed auth types for users/groups in the advanced settings of WinSSHD)

$ ssh-keygen -t rsa -C "Comment" Generating public/private rsa key pair. Enter file in which to save the key (/c/Users/shoehle/.ssh/id_rsa): Enter passphrase (empty for no passphrase): Enter same passphrase again: Your identification has been saved in /c/Users/shoehle/.ssh/id_rsa. Your public key has been saved in /c/Users/shoehle/.ssh/id_rsa.pub. The key fingerprint is:c5:ed:1b:d1:40:94:5b:a1:6b:d1:76:a1:46:8b:7b:fc Comment

The -t specifies the type. In this case RSA with a default length of 2048 bit.
And with the -C parameter you can add a comment.
The default file path should be fine so just press enter at the first prompt.
Then choose a good passphrase for your key.

5. Import the public key (id_rsa.pub) in WinSSHD to the user account you want to connect with

6. At this point you should be able to connect to your SSH server with the key. If you type ‘ssh username@server’ again you should be able to connect with the key + passphrase.

Ok so these are the basic steps to connect with git to your sever through SSH.
Also if you don’t want to re-enter the passphrase everytime you connect, have a look at this help article from Github

If you now try to clone/push/pull/etc. from the server you will very likely get some errors.
Something like “git-upload-pack: command not found” or “myrepo.git does not appear to be a git repository” or similar.
To fix the first error you can specify the path to the upload/receive pack on the server with some additional parameters. But more on this later.
The second error is due to the command that msysgit tries to execute on the shell. It has single quotes instead of double(or no) quotes that enclose the path to the repository and therefore Windows can’t execute it properly and throws an error. To fix this we use sh.exe from msys.

[Update 05.08.2011]: Here’s a follow-up post that shows an easier way to set up the server. So you can skip the below sections.

Making Git work on the server:

1. If not already done, install msysgit on your server (I would recommend to install it directly to C:\Git or at least a path that has no spaces because I had some weird issues with “spaced” paths)

2. Add C:\Git\bin to the PATH variable. This is very important!! sh.exe and other dependencies are in this folder

3. Now go to C:\Git\bin and add the following two files

gup.sh grp.sh

4. Open gup.sh in your favorite editor and insert

C:/Git/libexec/git-core/git-upload-pack.exe $*

5. Open grp.sh and insert

C:/Git/libexec/git-core/git-receive-pack.exe $*

The $* essentially rips off the single quotes from the repository path argument, so a path that has spaces in it won’t work here either I guess

Basically we’re done now and all git operations from the client should work.
For a clone you have to type

git clone -u 'sh gup.sh' ssh://username@server/path/to/myrepo.git

or a push would be

git push --exec 'sh grp.sh' ssh://username@server/path/to/myrepo.git

but that is not very elegant.

Cleaning things up:

1. At first we want to get rid of the whole repo path by specifying a remote alias

git remote add origin ssh://username@server/path/to/myrepo.git

Where “origin” would be the alias name

2. Next we set the config for the git-upload-pack and git-receive-pack so we don’t have to reference the shell script all the time.

git config remote.origin.uploadpack 'sh gup.sh'

and

git config remote.origin.receivepack 'sh grp.sh'

That’s it. Now we can use the normal git commands without any additional parameters:

git clone origin git push origin master git pull origin ...

Hurray!

Alternatively I could have gone with Cygwin + OpenSSH of course and there are some tutorials out there on how to set this up, but I don’t want to have the unnecessary Cygwin bloat on the server unless I really need to. Also these Cygwin tutorials seemed to be much longer than the approach I took.

Git, Git, Git

Today i decided to try out a new version control system: Git.

Git becomes more and more popular these days because of its speed, its decentralized structure and several other new approaches to version management. So I decided to take a first look at it. After reading through some articles about Git and its integration for Windows I created an account at Github and downloaded GitExtensions which includes the msysgit, a Git client for Windows. It also delivers a shell extension and a Visual Studio add-in. After I installed it I sadly discovered that there wasn’t a new entry in the context menu and in Visual Studio i also couldn’t recognize a new tab or something. Ok, so I restarted my PC. After that a Git tab appeared in Visual Studio but the shell extension still wasn’t there. Besides that the GUI was very slow. Every dialog loaded several seconds until it was usable. Not a good start with Git. But perhaps there are still some issues with Win7 x64. I uninstalled it from my Desktop PC but gave it a second chance and installed it on my laptop, which runs 32bit WinXP. And it worked. The shell extension, the VS add-in and without restart.

Ok, fine. But for my desktop that’s not much of use. Another interface to Git is TortoiseGit. I usually use TortoiseSVN + AnkhSVN for source control, so I had high expectations in this one. The first impression was quite good as it looked very familiar. But on second sight it seemed not so polished as I expected. The icon overlays didn’t work well and i couldn’t find the “git add” option to put changes to the staging area. Perhaps the unreliable behaviour is again due to my system, but in the end it didn’t convince me and I dropped it.

Now I’m just going with the normal tools from msysgit: Git Bash and Git GUI which are ok and quite uncomplicated to use. And the best of all, they work. I also found some nice introductions that illustrate the general use of msysgit and the setup of a repository at Github e.g. here or here.

I didn’t do that much operations with Git until now and it’s quite early to form a final opinion about it, but from what I saw it has much potential to establish itself also in the windows world provided that it will get a nice and friendly user interface and integration to VS. Besides the fact, that they didn’t work as intended on my machine, GitExtensions and TortoiseGit are doing good steps in that direction.

I really like the staging area or the uncomplicated setup of a new repository and creation of branches and I definitely will use it more often in the future.

Win7 GodMode?

As you might have noticed, there were many posts and comments on this topic around the internet lately. It’s a nice feature imo and worth a mention in here.

First of all, what is this ominous GodMode and how can I enable it?

The “GodMode” allows you to have a complete list of all Control Panel options in one folder. You can simply achieve this by creating a new folder and append “.{ED7BA470-8E54-465E-825C-99712043E01C}” to its name (don’t forget the dot). The folder name is irrelevant, you can name it whatever you like. Or you just paste “shell:::{ED7BA470-8E54-465E-825C-99712043E01C}” into the explorer address bar and press enter. You can then just drag the icon and put a shortcut whereever you like.

But this is not a so secret feature as you might think. It is documented in the MSDN along with many other GUIDs you can use the same way. You can also search google for “CLSID list” or similar things and you will find many other useful GUIDs. I personally linked my explorer shortcut in the Win7 taskbar to the “My Computer” folder which i think is much more useful than the default location. To do this you have to navigate to the “Windows Explorer” in the Start Menu (under Accessories) and open the properties. Then change the Target to: “%windir%\explorer.exe /root,::{20D04FE0-3AEA-1069-A2D8-08002B30309D}”.

Vista x64 users shouldn’t create a folder using the “GodMode” GUID, as the explorer will most likely hang-up. I don’t know if the other GUIDs will work or not. If you tried it anyhow you have to remove the folder by starting the Task Manger and open the command line by clicking on “File -> New Task (Run…)” and inserting “rd <folderpath>”.

If you just want a complete list of all Control Panel options, but don’t want to handle around with the GUIDs you can also simply open the Control Panel and type a small “a” into the search bar. Et voilà, same effect, less effort.

Howdy!

So, this is my first Post in my first Blog.

This blog shall serve as my private journal in the first place. It will focus on programming in the broadest sense. And if some people out there can make use of my entries, all the better.

I really had a hard time deciding whether i shall blog in english or in german. And I’m still not quite sure about it. But as you might have noticed I started out writing in english, so let’s just see what happens. It will also not hurt my english skills 😉

There are so many options and preferences you can set in the admin panel and that i don’t oversee at the moment. So the appearence of the blog might change by and by.

I think thats it for the moment. Gotta shovel snow now.

%d bloggers like this: