Stanford Algorithms I results

Just got my certificate from the instructor Tim Roughgarden who taught
Algorithms I via coursera.  I got 81.1% out of 100% based on exercises,
programming assignments and final exam.

Logging in parallel environment: identification of tasks without rewriting existing code

While working on parallel plugin support in a proprietary java execution framework
I was looking for a solution of having log messages produced by
tasks and other threads spawned by tasks have meaningful IDs that would
help one quickly identify groups of threads corresponding to a task.

So: single log file, multiple plugins, plugin may have multiple tasks,
task may create an unknown number of threads.  This is because while
we provide the parallel API to facilitate task creation, plugins
have their own freedom to create threads.

Ideally, we want the log file to have plugin id, and task id.
The problem is, when logging, how do we know what is the plugin id and task id.
When logger.log() is called, we have the stack frame, class loader, and
thread itself.  Looking further at these options:
1) Inspecting the entire stack frame and finding relevant objects on the stack
is too expensive
2) Classloader: we would have to have a classloader per task,
which we don't want to do since it interferes with other aspects of
the framework
3) Thread info: we have no control over thread creation, thread name, thread local.
E.g. we can't ensure that each time thread is created something is assigned
automatically to it, like a special name, thread local value, etc.
Except we can ensure it's put in the thread group of our choice if we
use security manager.

This turned out to be the most optimal solution.  Framework already had
security manager in place, and we could use it to assign each newly created
thread the group of its parent, and assign newly executed plugins and
plugin tasks a special groups.  In this way, once plugin task is started
in its own thread group, all threads it creates are placed in the same group.

[In practice, because no plugin code was ever using thread groups, it wasn't even
necessary to modify the security manager, because the default group is thread's group].

Alternative solution would be using something like logging context, like MDC in log4j
(we actually were using java logging).  It sets fields in ThreadLocal.  But that
would require modifications to existing code and ensuring all new code sets
that information correctly.  The MDC approach doesn't work well with thread pools:
the context needs to be transferred to the threads in the pool.

The disadvantage of ThreadGroup-based solution is that you cannot reuse threads.
E.g. you cannot have a thread pool for plugin tasks, because once thread is created
its group cannot be changed.  So it's impossible to reuse the thread for another task.
That was a small inconvenience, because java.util.concurrent Executors use thread
pools.  However it wasn't a performance inconvenience, because plugin tasks are
created where things are truly slow, so thread creation isn't an issue.

Should number of buckets be a prime number in a hash table

A little refresher. Given an object, we calculate its hash code, and given its hash code we find the bucket in the hash table. Usually we do it by taking the modulo of the hashcode:

bucket = hashcode % #buckets

If that's the case, the best way to ensure a decent distribution of keys is to choose a prime number for the number of buckets.  Proof follows later.

However, Java doesn't use the approach or using the mod function to map key to bucket, and they don't trust the quality of the original hashcodes, so they are modified further inside the hash map implementation.

Well, if bucket number had been determined using a mod operation, would it matter if number of buckets was prime?  Yes.

As an illustrative example, consider number 7 (prime) and 9 (non-prime) used as number of buckets.
Note what happens with hashcodes divisible by 3 and 7.

key  bucket                bucket
       (if 7 buckets)   (if 9 buckets)
3   3                   3
6   6                   6
7   0                   7
9   2                   0
14  0                   5
18  4                   0
27  6                   0

Because number 9 isn't prime, it can be expressed as 3 x 3,
so when we use keys that are multiples of 3, they all fall
in only 3 buckets (0, 3, 6).  Other keys are uniformly distributed
when bucket number is 9.


3                       3
6                       6
9                       0
12                      3
15                      6
18                      0
21                      3
24                      6
27                      0

When using number of buckets as 7, only multiples of 7 are put
in the same bucket (same as when multiples of 9 are put in
the same bucket).  The difference here that in case of non-prime number
of buckets there are more cases when keys are unevenly distributed.

A more formal proof could be along these lines:

modulo operation is
    mod(n) = r
if
    n = mq + r
above, m is number of buckets, so
    n = 9q + r
resulting bucket where key is mapped is
    r = n - 9q
what if we're only looking at multiples of 3, so k*3,
how to prove that there are fewer outputs:
    r = 3k - 9q
    r = 3(k - 3q)
So no matter what the input key is, the output is tripled,
which means that for every bucket for which key is mapped into,
there are two buckets that were skipped.