Meine Bachelorarbeit

Es ist lange her, dass ich das letzte Mal in diesem Blog einen Beitrag geschrieben. Deswegen kommen in der nächsten Beiträge über Dinge die liegen geblieben sind.

Anfang 2016 beendete ich das schreiben an meiner Bachelorarbeit mit dem Titel „Besser Benchmarken“ in deren Rahmen ich das Benchmarkingwerkzeug temci entwickelte.

Es ging in der Bachelorarbeit darum, dass die Anfertigung korrekter Benchmarks recht schwierig ist und deswegen ein Werkzeug zur Vereinfachung nötig ist. Solch ein Werkzeug ist temci, es erlaubt das einfache Erstellen von Benchmarks und eine einfache statistische Auswertung.

Außerdem ging es in der Arbeit um die (theoretischen) Grundlagen für gute Benchmarks. Diese Grundlagen habe ich dann auch in einem Vortrag auf der GPN 2016 vorgetragen:

 

GHC performance over time

Update: This post (and the bug report Joachim Breitner submitted in succession) resulted in the change of the haskell documentation: The statement „At the moment, -O2 is unlikely to produce better code than“ was removed from the documentation two months after this post. A denser and cleaner representation of the data and the main arguments is given in my bachelor thesis (written in german) that I finished around the same time.

TL;DR: There’s no significant difference between the GHC versions 7.* and 8.0.1-alpha regarding the Haskell code used in the benchmarking game. And there might be an improvement of the performance of idiomatic Haskell code from GHC 7.0.1 to GHC 8.0.1-alpha.

I’m currently building a new benchmarking tool called temci as part of my bachelor thesis.

In search for good programs to benchmark for the evaluation part, I stumbled across the benchmarking game. This blog posts is about using parts of the benchmarking game and temci to measure and compare the performance of the following GHC versions: 7.0.1, 7.2.1, 7.4.1, 7.6.1, 7.8.1, 7.10.1 and 8.0.0 (the version from mid January, called 8.0.1 here for brevity) using different optimization levels („-O“, „-O2“ and „-Odph“, see: Haskell documentation) . Weiterlesen

Gesprächsnotiz

Es fühlt irgendwie komisch an, wenn man denkt man wäre mit seinen post pubertären Probleme alleine und dann merkt, dass viele Leute schon vor Jahrzehnten die gleichen Probleme hatten und sich die gleichen Fragen gestellt. Der Mann mit dem ich heute durch Zufall am Vögel beobachten (und Stanislav Lem lesen) redete war jenseits der 70 Jahre.

Music of the week – Plumes Ensemble

In dieser Kategorie meines Blogs stelle ich jede Woche kurz eine Band vor, deren Musik ich in jener Woche am liebsten hörte.

Das Plumes Ensemble spielt eine schöne Mischung aus Klassik und melodischem Indie Pop. Es stammt, wie ihre Frontsängerin Veronica Charnley, aus dem kanadischen Montréal.

Hier das Musikvideo zum aktuellem Album Plumes.

Das Ensemble spielte vor wenigen Wochen im Nun Cafe in Karlsruhe. Durch diesen Auftritt bin ich auf es erst aufmerksam geworden, wobei ich leider erst zu kurzfristig davon erfuhr und deswegen nicht dort sein konnte.

The Pumping Lemma – Poem by Harry Mairson

Any regular language L has a magic number p
And any long-enough word in L has the following property:
Amongst its first p symbols is a segment you can find
Whose repetition or omission leaves x amongst its kind.

So if you find a language L which fails this acid test,
And some long word you pump becomes distinct from all the rest,
By contradiction you have shown that language L is not
A regular guy, resiliant to the damage you have wrought.

But if, upon the other hand, x stays within its L,
Then either L is regular, or else you chose not well.
For w is xyz, and y cannot be null,
And y must come before p symbols have been read in full.

As mathematical postscript, an addendum to the wise:
The basic proof we outlined here does certainly generalize.
So there is a pumping lemma for all languages context-free,
Although we do not have the same for those that are r.e.

There are some other poems by Harry Mairson at http://www.cs.brandeis.edu/~mairson/poems/poems.html. I found this poem while reading a discussion at The Old Joel on Software Forum.

Real life practice in lottery scheduling

I currently have a course covering operating systems at university. We learn in this course several scheduling algorithms. An operating system needs these kind of algorithms to determine which process to run at which time to allow these process to be executed „simultaniously“ (from the users view).

Good scheduling algorithms have normally some very nice features:

  • They avoid the starving of one process (that one process can’t run at all and therefore makes no progress).
  • That all processes run the approriate percentage (defined by it’s priority) of time in each bigger time interval.

But they are maybe not only useful for operating systems but also for people like me. Probably they could help me to improve the scheduling of my learning.

An algorithm that seems to be suited best for this purpose is called lottery scheduling (pdf). It’s an algorithm that gives a each process some lottery tickets (their number resembles the priority of the process). Every time the algorithm has to choose a new process to run, it simply picks a lottery ticket randomly and returns the process that owns the ticket. A useful addition is (in scenarios with only a few tickets) to remove the tickets that are picked temporarily from the lottery pot and put them back again, when the pot is empty.

But how could I use this algorithm in practice?

I take a stack of blanko cards, each card worth around 2 hours of learning time, and assign them to each of my courses. E.g. the course operating systems gets 3 cards, out of the 25 cards that now make up my week.

Now, when I’ve time to learn, I pick a card out of the shuffeled card stack which then tells me to learn about 2 hours e.g. for my theoretical computer science course.

This „practical exercise“ in operating systems will hopefully boost my learning – and of course is funny way to learn, as I never know what I’m going to learn. Later, I probably also could use it to ensure that I’m blogging more regularly here and progress with my compiler project.