Grundlagen der Darstellungstheorie von endlichen Gruppen

March 24, 2013 Leave a comment

Nachdem doch einiges an Arbeit darin steckt, habe ich mich entschlossen meine Bachelorarbeit in Mathematik über die Grundlagen der Darstellungstheorie von endlichen Gruppen unter einer Creative Commons Lizenz online zu stellen. Vielleicht hat ja irgendjemand dadurch einen Nutzen. Wer Fehler darin findet, und solche gibt es ganz bestimmt genug, möge mich darauf hinweisen, auch dann wenn es sich um Trivialitäten handelt.

Advertisements
Categories: Mathematics Tags:

Series About Java Concurrency – Pt. 6

February 15, 2013 Leave a comment

This is the solution to my previous post, so make sure that you read it before you continue. For your convenience, here is the program we are going to discuss once again:

public class ThreadNoMore extends Thread
{
    private static final int N_THREADS = 16;
    private static final AtomicInteger threadsStarted = new AtomicInteger();
    
    private final long ctorThreadId = Thread.currentThread().getId();
    
    @Override
    public synchronized void start()
    {
        if(ctorThreadId != Thread.currentThread().getId())
            threadsStarted.incrementAndGet();
    }
    
    public static void main(String[] args) throws InterruptedException
    {
        Thread[] threads = new Thread[N_THREADS];
        for(int i = 0; i != N_THREADS; ++i)
            threads[i] = new ThreadNoMore();
        
        for(Thread th : threads)
            th.start();
        
        for(Thread th : threads)
            th.join();
        
        System.out.println("threadsStarted: " + threadsStarted);
    }
}

As already pointed out by Ortwin Glück, the program always prints

threadsStarted: 0

because ThreadNoMore.start() is always executed in thread that invoked it. And if you think that over twice, this should not surprise you at all, as methods are always executed in the thread that invoked them. This even applies to Thread.run(), which is the method we should have overridden instead, but unlike Thread.start(), Thread.run() is normally invoked by the Java Virtual Machine, as the Javadocs for Thread.start() tell us:

Causes this thread to begin execution; the Java Virtual Machine calls the run method of this thread.

So apart from not doing what we might have intended, carelessly overriding Thread.start(), that is without calling super.start(), so that the JVM can do its magic, leaves us with a crippled class, that no longer has anything to do with a thread at all. Considering these facts, it should not take you by surprise that

public class Thrap extends Thread
{
    private static final int N_THREADS = 42;
    
    private static final AtomicInteger 
        started = new AtomicInteger(),
        ran = new AtomicInteger();
    
    @Override
    public synchronized void start()
    {
        started.incrementAndGet();
    }
    
    @Override
    public void run()
    {
        ran.incrementAndGet();
    }
    
    public static void main(String[] args) throws InterruptedException
    {
        Thread[] threads = new Thread[N_THREADS];
        for(int i = 0; i != N_THREADS; ++i)
            threads[i] = new Thrap();
        
        for(Thread thread : threads)
            thread.start();
        
        for(Thread thread : threads)
            thread.join();
        
        System.out.println("started: " + started);
        System.out.println("ran: " + ran);
    }
}

results in

started: 42
ran: 0

being written to your terminal. As you can see clearly, Thrap.run() is not executed at all, neither from a newly created, nor from the main thread. The fix the code above, you have to call super.start() in Thrap.start() like so:

    @Override
    public synchronized void start()
    {
        super.start();
        startedThreads.incrementAndGet();
    }

After this modification you get

started: 42
ran: 42

as expected.

So what can we learn from all of this? At first, there are two things to remember about the Java threads API:

Equally important are the consequences for API design: Interfaces should be easy to use correctly and hard to use incorrectly. Unfortunately the Thread class violates this principle, as it is quite easy to misuse as we have just seen. More generally, requiring clients to call the super version of a method they are overriding is considered to be an anti pattern for this very reason.

Categories: Programming Tags: , ,

Series About Java Concurrency – Pt. 5

February 13, 2013 1 comment

After quite some time, here is a concurrency related puzzle once again: Take a look at the following program and try to predict its output:

package com.wordpress.mlangc.concurrent;

import java.util.concurrent.atomic.AtomicInteger;

public class ThreadNoMore extends Thread
{
    private static final int N_THREADS = 16;
    private static final AtomicInteger threadsStarted = new AtomicInteger();
    
    private final long ctorThreadId = Thread.currentThread().getId();
    
    @Override
    public synchronized void start()
    {
        if(ctorThreadId != Thread.currentThread().getId())
            threadsStarted.incrementAndGet();
    }
    
    public static void main(String[] args) throws InterruptedException
    {
        Thread[] threads = new Thread[N_THREADS];
        for(int i = 0; i != N_THREADS; ++i)
            threads[i] = new ThreadNoMore();
        
        for(Thread th : threads)
            th.start();
        
        for(Thread th : threads)
            th.join();
        
        System.out.println("threadsStarted: " + threadsStarted);
    }
}

The solution, together with a detailed explanation will be available soon.

Categories: Programming Tags: , ,

The IP SQUARE Commons Java Libraries

January 31, 2013 Leave a comment

The purpose of this post is to introduce the ipsquare-commons project , a small collection of reusable Java classes I’ve put together while working at IP SQUARE. As there are tons of useful Java libraries already out there, and I prefer to use these whenever reasonably possible, you shouldn’t expect anything too fancy, as the exciting problems the everyday Java developer has to deal with have already been solved elsewhere.

As of today, the ipsquare-commons project consists of the following modules, that are separate artifacts and are introduced in the manuals linked below:

All related artifacts can be found in the Maven Central Repository.

Categories: Programming Tags: ,

Series About Java Concurrency – Pt. 4

May 19, 2011 6 comments

This post is the solution of Series About Java Concurrency – Pt. 3, so be sure to read my last post before this one.

So, what does the code from Series About Java Concurrency – Pt. 3 do? As it turns out, there isn’t a single answer: If you are using a recent Oracle VM the behavior of the program seems to depend on whether your VM runs in server or client mode. In client mode the program will most likely stop after roughly 2.5s as one would naively expect. In server mode however, the program just loops forever. The update to stop in line 24 never gets visible to the main thread. This isn’t a bug, but perfectly legal behavior according to the Java Memory Model, which allows optimizing

while(!stop)

into

while(true)

Synchronization is not just about avoiding data races; it is also needed to avoid reading stale data. This may sound weired, but allows the VM as well as the CPU to apply powerful optimizations (for example Out-of-order execution) that would otherwise be impossible or very hard to implement.

One way to fix our shiny little program is by using the synchronized keyword as demonstrated below:

package com.wordpress.mlangc.concurrent;

public class PleaseWait
{
    private static final long MILLIS_TO_WAIT = 2500;
    private static boolean stop = false;
    
    private static synchronized boolean isStop()
    {
        return stop;
    }
    
    private static synchronized void setStop(boolean stop)
    {
        PleaseWait.stop = stop;
    }
    
    public static void main(String[] args)
    {
        Thread timer = new Thread(new Runnable()
        {
            public void run()
            {
                try
                {
                    Thread.sleep(MILLIS_TO_WAIT);
                }
                catch(InterruptedException e)
                {
                    // We are already exiting the thread.
                }
                finally
                {
                    setStop(true);
                    System.out.println("Stop requested.");
                }
            }
        });
        
        timer.start();
        
        long start = System.currentTimeMillis();
        while(!isStop())
            ; // <-- Do nothing.
        
        long stoppedAfter = System.currentTimeMillis() - start;
        System.out.printf("Stopped after %dms.\n", stoppedAfter);
    }
}

It is important to note that both the setter and the getter are synchronized using the same lock. Synchronizing only the setter method is not enough!

While the code above works reasonably well, we can still do better because we don’t need mutual exclusion, but just want to ensure that main thread sees what the timer thread does. This can be accomplished quite easily by declaring stop to be volatile. The volatile keyword makes sure that the main thread always sees to most recent value of stop without any additional uses of synchronized. Following this advice, we end up with something like this:

package com.wordpress.mlangc.concurrent;

public class PleaseWait
{
    private static final long MILLIS_TO_WAIT = 2500;
    private static volatile boolean stop = false;
    
    public static void main(String[] args)
    {
        Thread timer = new Thread(new Runnable()
        {
            public void run()
            {
                try
                {
                    Thread.sleep(MILLIS_TO_WAIT);
                }
                catch(InterruptedException e)
                {
                    // We are already exiting the thread.
                }
                finally
                {
                    stop = true;
                    System.out.println("Stop requested.");
                }
            }
        });
        
        timer.start();
        
        long start = System.currentTimeMillis();
        while(!stop)
            ; // <-- Do nothing.
        
        long stoppedAfter = System.currentTimeMillis() - start;
        System.out.printf("Stopped after %dms.\n", stoppedAfter);
    }
}

The only difference to the broken version from Series About Java Concurrency – Pt. 3 is the volatile keyword in line 6.

Last but not least I want to state clearly that this article is not about the proper way to implement task cancellation, which is a nontrivial topic of it’s own. If parts of this post are new to you, I strongly suggest that you grab yourself a copy of the excellent book Java Concurrency in Practice and read at least the first chapter called Fundamentals thoroughly. By doing so you are almost certainly saving yourself from nasty surprises or frustrating debugging session in the future.

Categories: Programming Tags: , ,

Series About Java Concurrency – Pt. 3

May 10, 2011 8 comments

As it seems that even experienced Java programmers might have serious misconceptions regarding the Java memory model, I’ve decided to publish a concurrency related puzzle once again. Consider the following simple program and try to predict it’s output:

package com.wordpress.mlangc.concurrent;

public class PleaseWait
{
    private static final long MILLIS_TO_WAIT = 2500;
    private static boolean stop = false;
    
    public static void main(String[] args)
    {
        Thread timer = new Thread(new Runnable()
        {
            public void run()
            {
                try
                {
                    Thread.sleep(MILLIS_TO_WAIT);
                }
                catch(InterruptedException e)
                {
                    // We are already exiting the thread.
                }
                finally
                {
                    stop = true;
                    System.out.println("Stop requested.");
                }
            }
        });
        
        timer.start();
        
        long start = System.currentTimeMillis();
        while(!stop)
            ; // <-- Do nothing.
        
        long stoppedAfter = System.currentTimeMillis() - start;
        System.out.printf("Stopped after %dms.\n", stoppedAfter);
    }
}

The solution, together with explanations will be published in the near future.

Categories: Programming Tags: , ,

When True Is Not True Anymore

July 18, 2010 13 comments

We all know that accessing uninitialized variables in C and C++ usually leads to some kind of undefined behavior one usually wants to avoid. What I didn’t know until recently is that uninitialized bool values might be especially malicious beasts. To see what they can do to you, take a look at the following program, and try to predict its output:

#include <string>
#include <iostream>

using namespace std;

namespace {

    inline string stringify(const bool value)
    {
        return (value ? "true" : "false");
    }

    struct Struct
    {
        long l;
        bool u;
    };
}

int main()
{
    Struct s;

    if(true != s.u)
        cout << stringify(true) << " != " << stringify(s.u) << endl;
}

Now type g++ stringify.cc -o stringify and run the generated executable. Here is what you might see on some platforms:

$ ./stringify 
true != true

Yes, you got that right true != true! I get this behaviour with g++-4.3 and g++-4.4 on Gentoo (x86 and x86_64) as well as with g++-4.1 and g++-4.4 on Ubuntu 9.10 (x86_64). Before attempting to explain what happened here, I want to summarize a few additional facts:

  • Several attempts to make this program shorter without ending up with something boring failed.
  • Turning on optimization causes g++ optimize all if statements away (especially the implicit one in stringify) under the assumption that s.u is false, which again leads to a much more sane output.
  • I could not reproduce this with icc-11.1.

So, what happened? Is g++ broken? Actually the answer is no. Accessing uninitialized memory leads to undefined behavior, and undefined means undefined. In fact the C++0x Final Committee Draft contains a footnote that explicitly mentions the oddity we have just seen:

47) Using a bool value in ways described by this International Standard as “undefined,” such as by examining the value of an
uninitialized automatic object, might cause it to behave as if it is neither true nor false.

This is not that surprising if one considers that at assembler level, a bool is not represented by a single bit, but at least by a byte. An uninitialized byte might have 256 different values, and not just two. One could of course consistently map 0 to false and everything else to true, but this is not what g++ does. To see what I mean, take a look at the following assembler snippet, that g++ generated for the if statement in line 24:

movzbl  -40(%rbp), %eax  # move s.u to eax.
xorl    $1, %eax         # xor eax with 1.
testb	%al, %al         # check if the low byte of eax is 0.
je      .L8              # jump to .L8 if so.

If the jump is taken, the body of the if statement in line 24 is skipped, otherwise it is executed. Now the xorl in line 2 switches the lowest bit in eax, leaving all other bits unchanged. Therefore s.u is considered to be equal to true if and only if it has the byte value 0x01.

Now lets take a look at the assembler that represents the ternary operator in stringify:

cmpb $0, -36(%rbp)    # compare the argument with 0.
je   .L2              # jump to .L2 if the argument is 0.
movl $.LC0, %eax      # store "true" in eax.
jmp  .L3              # jump out.
.L2:
     movl $.LC1, %eax # store "false" in eax.
.L3:

Here g++ maps 0 to false and every other value to true. This means that if the actual byte value of s.u is for example 0xFF (which for some reason is what cgdb keeps telling me locally), the if in line 24 will be taken as if s.u was false, but stringify will behave as if s.u was true.

Categories: Programming Tags: