Simply Explained : Multithreading

John and Mary both walk into work. Let’s consider both John and Mary to be a “thread”. We’ll define a “thread” to simply be a sequence of consecutive actions. In this case, let’s say that John is a “thread”, and Mary is also a “thread”, because they can both execute actions in parallel. If John is working on a spreadsheet, Mary does not have to wait for John to finish before she can do her own tasks. They are both independent entities.

Now, John loves donuts. Fortunately for John, his company always stocks donuts in the company fridge. For John, his thought process is quite simple, and looks like this :

if John sees at least one donut in the fridge
    then John washes his hands
    then John grabs a donut and eats it

And this is fine and dandy. When John is alone, this course of logic always works. He sees a donut in the fridge, he washes his hands, and he eats it. It always works without fail.

However, one day, Mary walks into the room. And Mary also likes donuts. When John looks into the fridge and sees that there is exactly one donut left, he hurriedly goes to wash his hands. However, when he returns, he finds that the donut is gone! But that shouldn’t have been possible. John had checked that at least one donut existed before he decided to wash his hands to eat it!

So what happened? It turns out that Mary had taken the donut in the time that John had spent washing his hands. This is the problem with multithreading, which is the act of programming with more than one thread.

 


The Problem with Multithreading


While it may be true that John’s logic always succeeds when he is alone (single-threaded), the same cannot be said when Mary is with him (multithreaded). This is because when objects are shared between multiple threads, multiple different threads are able to modify the object at the same time. In this case, the fridge is the object, and both John and Mary are able to modify the contents of the fridge at any time.

This is a huge problem, because now, functions that had been unit tested or proven to work on a single thread no longer work when multithreaded. As shown above, doing secure checks like putting in defensive if statements is entirely ineffective, because the object can be modified right after your if statement is completed due to the fact that multithreading allows everything to be done in parallel.

So how can John prevent Mary from modifying the contents of the fridge until he is done using it? The answer is fairly simple — when John accesses the fridge, he needs to make sure that he is the only one who has control of it until he is done whatever he is doing. There are multiple ways to do this, but the most common is to use something called a “lock”.

This new multithreaded system with locks has three simple rules :

1. Whoever controls the lock will have sole control over the object for as long as they possess the lock.
2. An object should only have one lock.
3. Any thread waiting on a locked object can either throw an exception or wait for it to be unlocked. In which case, it will be passed by some priority order (usually first come first serve, like a queue).

Let’s observe why these three rules are true.

 


Rule Number One


“Whoever controls the lock will have sole control over the object for as long as they possess the lock.”

The first rule is true because that is how a lock is defined. But for a more intuitive approach, you can think of the lock as “binding” itself to its owner. As long as the owner of the lock does not relinquish control, the object will forever be locked. This also means that if a thread controlling a locked object gets stuck in an infinite loop, that locked object will be locked forever.

Of course, while you could manually unlock the object, there is no way to determine if an object will be locked forever, because you can’t (in general) determine whether or not a thread is stuck in an infinite loop (see Halting problem).

 


Rule Number Two


“An object should only have one lock.”

Suppose an object could have two separate locks that give complete access over the object. That means that two different threads can access the object at the same time. Unfortunately, this is essentially no different than not having a lock at all, because now the object can be freely edited at any time by anyone. We are back to the exact same problem that we initially started with!

This means that an object must have one and only one lock, and only one owner for that lock.

 


Rule Number Three


“Any thread waiting on a locked object can either throw an exception or wait for it to be unlocked. In which case, it will be passed by some priority order (usually first come first serve, like a queue).”

In general, it is bad practice to have your code throw an exception when it attempts to access a locked object. The more conventional approach is to create a queue for that locked object, like a wait list. This is so that if three threads wanted to access an object, they would access the object in the order that they called the lock.

For example, the execution order might look like this :


1. Thread 1 calls for the object. It is not locked, so Thread 1 gains control of the lock.
2. Thread 2 calls for the object. It is locked. Thread 2 is put on the queue (wait list)
3. Thread 1 performs some operation using the object.
4. Thread 1 relinquishes control of the lock.
5. Thread 3 calls for the object. It is unlocked at this very exact moment, but because there is a queue for this object, the lock goes to the first element in the queue, which is Thread 2. Thread 3 is now put on the queue.
6. Thread 2 performs some operation using the object.
7. Thread 2 relinquishes control of the lock.
8. Thread 3 automatically gains control of the lock, as Thread 3 is next on the queue.
9. Thread 3 performs some operation using the object.
10. Thread 3 relinquishes control of the lock.


As you can see, when multiple threads want access to a locked object, they are accessed in first-come-first-serve order. However, this does not necessarily mean that Thread 2 just has to twiddle its thumb and do nothing. Thread 2 does not have to be blocked while it waits — it can do other computations while it waits for its access to the locked object.

This is important for when the desired operation could take a long time. For example, imagine if Thread 1 wanted access to an object controlling the webcam for your computer. Thread 1 could be using this object for a long time, and if Thread 2 and Thread 3 both sat idly doing nothing, we would experience a severe loss in performance.

 


Conclusion


In this article, you’ve learned that multithreading is difficult because if two threads access an object at the same time, there’s no guarantee that the object will give you the desired behavior. To fix this problem, you simply have to use a lock, which will prevent other threads from accessing the object. When a thread is done performing operations with a locked object, it relinquishes the lock, and the next thread gets control of the lock.

In the next Simply Explained post, I’ll be talking about Futures, which is a programming construct used to obtain a value that does not yet exist (for example, because the object you wanted to use to get that value was locked). It allows you to write non-blocking code, because after you create a Future, your thread can do other tasks until the Future makes a callback, telling you that the value now exists.

Happy coding, and enjoy your new-found multithreading powers.

Advertisements

Common Boat Anchors in Programming and How to Avoid Them

A boat anchor is a metaphor that describes something that is obsolete or useless. In programming, boat anchors are everywhere. If you aren’t careful, boat anchors can ruin your productivity and cause confusion. Luckily, boat anchors are easy to prevent and correct if you look out for them. With just a little bit of foresight, you too can preserve your sanity.

TODO comments


Everyone’s used it. A seemingly innocent TODO comment. No harm done, since it’s just a little reminder for yourself right?

Wrong.

TODO comments are not only useless, but a productivity sink as well. Firstly, the “TODO” that you gave for yourself usually never gets done, as it’s buried in some function or class that you probably won’t even revisit for another week or two. Even if you do see the TODO, you’ll most likely ignore it as you’ll be too focused on your current task.

Secondly, TODO comments are bad because they waste the reader’s time. TODO comments belong in a Trello board or some other organizational system, not in your code base. No one wants to waste time reading about something that you should have/want to have done, but never got around to.

Commented Code


In this day and age, if your organization uses GitHub or some other form of version control, commented code is absolutely useless. This isn’t referring to commenting your code with useful English messages, but rather commenting out chunks of runnable code.

Commented code is essentially noise for the reader. If you push commented code to your repository because you think you might “need it later”, then you are ignoring the key purpose of version control.

Version control saves code. If you ever need that snippet of code that you deleted two months ago, it’s easily accessible. Don’t comment out code, or you’ll end up with hundreds and hundreds of obsolete lines of code.

Uncommented Code That Is Unused


Imagine you’ve written a utility class that calculates mortgages for you.

Suddenly, you’re told that the feature is scrapped, but that it might make a reappearance in the future.

Upon hearing that it might be used again in the future, you decide to leave the utility class in the code, since you might “need it later”. Once again, this goes back to the idea of version control. If it’s not relevant, and if it’s never used or referenced, then it doesn’t belong in your repository. Delete it.

Obsolete Documentation


Let’s say you have a nifty little method that method that divides every number in a list by 4.

def list_divide(list, dividend):
  """
  Divides every number in a list by a
  dividend and returns a new list with 
  the resulting numbers.
  """
  ret_list = []
  
  for num in list:
    ret_list.append(num/dividend)
  
  return ret_list

Suddenly, you remember about division by zero and quickly add a check to your function.

def list_divide(list, dividend):
  """
  Divides every number in a list by a
  dividend and returns a new list with 
  the resulting numbers.
  """

  if dividend == 0:
    print("Dividend must not be zero.")
    return

  ret_list = []
  
  for num in list:
    ret_list.append(num/dividend)
  
  return ret_list

Unfortunately, since you didn’t update the documentation, the docstring is now a lie. It doesn’t tell the user what the function actually does. There is no reference to division by zero in the docstring, causing the documentation to become a boat anchor.

Outdated documentation causes all sorts of issues for users. Luckily, this issue is easy to resolve. As a rule of thumb, if you add additional functionality to a function, document it. Even if you don’t like documentation, or if you think it’s tedious and pointless, do it anyway. You’ll save other programmers from headaches and wasted time.

Adding Ticket Numbers as Comments


Although not extremely common, some people feel the need to compulsively comment every change they make with a ticket number.

For example, you might see something like this :

#Added foobar function to resolve ticket 53
def foobar(num):
  #Fixes ticket 281
  if num == 0:
    print("Hello World!")
  elif num == 3:
    #Added because of ticket 571
    print(num/9)
  #Added else because of ticket 1528
  else:
    #Due to ticket 4713, changed to 'Goodbye World!' 
    print("Goodbye World!")

Before long, everything in your code will have a comment regarding a ticket.

If you are guilty of doing this, stop it. No one cares what ticket number the fix was in. Make the fix, commit, and push. All of the comments about tickets and issue numbers are utterly pointless and end up as unnecessary noise to the reader.

If you feel that the change is so strange or quirky that you absolutely must give some sort of background information, then write a comment. Making the reader search up a specific ticket to understand the code is a gigantic time sink, especially since most tickets have multiple comments. No one wants to read through all that text. Summarize it in a single comment and move on.

Storing Variables For No Reason


It’s a common practice for developers to do something along the lines of this :

def foobar(num):
  return num * 13

#Doing this
num = foobar(32)
print(num)

#As opposed to
print(foobar(32))

In this case, as long as “num” is not set to some wildly long function call, there is no reason to store it as a variable. In this case, foobar(32) is short, so it should be directly inputted into another function, rather than being set to a variable, and then inputted into the function.

Assigning it to a variable when the functional call is short tells the reader, “The variable num is important. It will be reused later in some way somewhere down the line.”

Not only that, but unnecessarily creating variables adds extraneous code for no good reason.

Conclusion


Boat anchors are everywhere in code. If you can avoid them, you will make not only your life easier, but everyone else’s as well. No one wants to waste time reading excessive code. Reading code is already difficult. Making your peers read more code than necessary hurts their productivity and makes coding an unpleasant experience.

So be a good person. Prune off the excess and correct the outdated. If you find any excessive code, then remove it. If the documentation is inaccurate or outdated, fix it. It might be a thankless job, but know that you’ll have made the world just a little brighter in the process.

Null Island – The Most Famous Island that Doesn’t Exist

It’s been a long and tiresome week of work, and you want a vacation.

You search online for some decent vacation spots.

Hawaii? Nah. Canada? Already been there.

But hold on, something catches your eye. Null Island? Thousands of visitors? And look at that population density! All those posts from (0,0)?

And so you set out on an arduous and dangerous journey to Null Island, only to find this.

Null-island-buoy
Photo from Wikipedia

Yep. Null Island, the most popular tiny island you’ve found in your life, doesn’t exist.

What’s Going on Here?

Null Island, located with the geographic coordinates (0,0), is a byproduct formed by bad programming.

How did it happen?

Some developers who were creating a GPS system decided that, if a person’s coordinates couldn’t be found, that instead of setting them (Null, Null), they were instead set to (0,0).

In psuedocode, it went down something like this :

if user's x coordinate is Null
  set user's x coordinate to 0

if user's y coordinate is Null
  set user's y coordinate to 0

Not only is this kind of code an anti-pattern, but for something such as position tracking, this can have serious consequences.

For example, in Wisconsin, many voters were in locations that did not have registered coordinates. However, in order to vote, they needed to use a new geocoding system that tied their house address to a geographical coordinate.

Unfortunately, the Wisconsin voters were given a geographical coordinate of (0,0), or Null Island. For a population of nearly 6 million, the problem was quickly discovered and fixed, but it is yet another example of how bad programming can wreck havoc.

To prevent mistakes like these, ask yourself if what you’re doing makes sense in a different context.

Here are some similar scenarios, using the same logic that caused the Null Island issue.

if user's phone number is Null
  set user's phone number to 000-000-0000

if user's pin number is Null
  set user's pin number to 0000

if user's credit card number is Null
  set user's credit card number to
    0000 0000 0000 0000

In scenarios where the 0 is significant, you cannot replace null with zero. If your wallet is null, it means you don’t have any money. Your balance is 0. If your friend count is null, it means you have no friends, so your friend count is 0.

However, if the zero matters, such as in a phone number, you can’t set the user’s phone number to 000-000-0000. Similarly, if you have an expensive watch, and the price is null because it’s not for sale, that doesn’t mean your watch costs $0.00. That would imply that you’re giving it away for free.

Conclusion

Null Island is a silly coding mistake that carries significant consequences, even today.

That’s not to say that every single mistake you make will effect an entire state’s voter population, but it can happen.

If you want to avoid creating the next equivalent of Null Island, leave your user’s input as is instead of attempting to change it. Null means null. Leave it as null.

Bogosort : Moving At The Pace of a Random Snail

Bogosort is a sorting algorithm, much like quick sort, and merge sort, with a twist.
It has an average case performance of O((n+1)!).

Bogosort is known by many other names, including stupid sort, monkey sort, and permutation sort.

Knowing this critical information, let’s dive into the meat of this sorting algorithm.

How Does It Work?


Bogosort works by taking an input list, and checking if it is in order. If it is, then we are done, and the list is returned. This means that Bogosort has a best case performance of O(n).

If the list isn’t in order, then we will shuffle the list until we get a list that is sorted. Unfortunately, since the list will be shuffled randomly, Bogosort technically has a worst case performance of O(∞).

 

Implementation


Bogosort’s implementation is short and concise.

import random

def Bogosort(list):
    while not isSorted(list):
        random.shuffle(list)
    return list

def isSorted(list):
    if(len(list) <= 1):
        return True

    if(list[1] >= list[0]):
        return isSorted(list[1:])
    else:
        return False

Simple and crisp. Let’s try it on some inputs.
Note that I used Python’s time module to print out the time, which is quick and dirty, but it does the job.

Bogosort([5,4,3,2,1])
Time = 0.000202894210815

Okay. Now let’s try it again on an input size of 10.

Bogosort([10,9,8,7,6,5,4,3,2,1])
52.8398268223

Since it is completely randomized, running this will give different times each time it is run, but the ballpark figure will at least be somewhat similar.

Normally, I’d try on a larger input size, but since the growth rate is going to be exponential, an input size of 11 will cause a time that is much longer than when an input size of 10 is used.

In fact, in our example, running on an input size of 10 took over 260,000 times longer than when run on an input size of 5.

However, since the numbers are random, it is impossible to determine exactly how much longer it will take , but it should be somewhere around that range.

Conclusion


If you are looking for a horrendously slow sorting algorithm for any reason, Bogosort is the perfect candidate. It works by randomly shuffling the list until it gets a sorted list, which means that its average performance is going to be O((n+1)!).

Of course, Bogosort should not be taken as a serious sorting algorithm, and is intended to be used as a comparison to other sorting algorithms like quick sort and merge sort.

Unless your goal is to create slow code, stay far far away from this monstrosity.

 

Java Lambdas : Syntactic Sugar

You glance down at your list of invited guests for your party.
Suddenly, you see someone with the last name of “Dang”, the very same family that ruined your party the last time they showed up.

Furiously, you write a program to sort through the hundreds of invited guests to remove everyone with the last name “Dang”.

For the sake of simplicity, a smaller list will be used, but nonetheless, you end up with this hideous snippet:

public class Party {

    static List invitedGuests;

    public static void main(String[] args){

        invitedGuests = new ArrayList() {{
	    add("Henry Dang");
            add("Joe Dang");
	    add("Kevin Smith");
	    add("John Dang");
	    add("John Doe");
	    add("Michelle Sans");
        }};

	for(Iterator iterator = invitedGuests.iterator(); iterator.hasNext();){
            String guestName = iterator.next();

	    if(guestName.contains("Dang")){
                iterator.remove();
	    }
	}

	for(String guests : invitedGuests){
	    System.out.println(guests);
	}
    }
}

 

What a terribly cluttered mess!

But what if you could have done it in a simpler, more concise way?
With Java 8’s lambdas, you can cut down the length of the logic to 1/5th of its size!

public class Party {

    static List invitedGuests;

    public static void main(String[] args){

        invitedGuests = new ArrayList() {{
	    add("Henry Dang");
            add("Joe Dang");
	    add("Kevin Smith");
	    add("John Dang");
	    add("John Doe");
	    add("Michelle Sans");
        }};

     invitedGuests.removeIf(name -> name.contains("Dang"));
     invitedGuests.forEach(name -> System.out.println(name));
    }
}

Just like that, your code instantly becomes clean, concise, and expressive.
The removeIf method simply takes a Predicate, which is basically a boolean. It checks if the name contains the word “Dang” in it, and if it does, it instantly removes it from the list.

The line after it is just a fancy for each loop, except it’s only one line long. The forEach method takes in a Consumer object, which basically says, “Give me a parameter, and something to do with that parameter.” You pass in the parameter “name”, and print all the names in the list.

Now that you’re done, all the Dangs are off your list, and you’ve shortened your otherwise obnoxiously verbose code by 8 lines.