# ROB 502: Programming for Robotics: Class 16

### Clicker Questions

1. How many different outputs are possible for the following program?
``````int number = 0;

for (int i = 0; i < 9; i++) {
number += 1;
}
}

for (int i = 0; i < 9; i++) {
number += 10;
}
}

for (int i = 0; i < 9; i++) {
number += 100;
}
}

int main(void) {

printf("%d\n", number);

return 0;
}
``````

In theory, when dealing with multiple threads, there are no guarantees about the order that they run in, or for how long any thread runs when it does run. The operating system may choose to run them all on separate processor cores simultaneously, or it might choose to run them all on a single core, and alternate between them and other processes. This is all unpredictable to your program, since you also can’t know for sure what operating system your program will run on. So it is possible for any ordering of thread executions to happen. For example, by the time the main thread goes to print `number`, each thread may have run any number of loop iterations, modifying `number`. So it is possible for any of 1000 different numbers to be printed out, including every number from 0 to 999.

1. In practice, what do you think are the most likely results? (if you have more than one, put them in order from most to least likely)
My personal guess was that 0 would be the most likely result, because perhaps the newly created threads would not have a chance to run before we get to the `printf`. In practice on my laptop, however, I got the numbers 9 and 99 about 50% of the time each. On one occasion I also got 90 as a result. This happens because running `pthread_create` itself is relatively slow, and so starting `thread3` gives `thread2` a chance to run, and starting `thread4` gives `thread2` and `thread3` a chance to run. Because the threads themselves have such short and fast loops, it is very likely that if the thread runs at all, it will run to completion. `thread2` seems to always run to completion, and `thread3` runs to completion about half the time. Apparently in a rare case, `thread2` didn’t manage to run, while `thread3` did, giving the result of 90, but `thread4` doesn’t have anything happen after it, and so doesn’t have enough time to run and do anything before the `printf`.

We will now use the following pseudo-program:

``````ht = hashtable_create()

word = block of memory for 256 characters
last_word = block of memory for 256 characters
for each word in "file" copied/read into word:
if not first word in file:
bigram = combination of last_word, " ", and word
if bigram in ht:
ht[bigram] += 1
else:
ht[bigram] = 1
copy word into last_word

# We are not calling hashtable_destroy at the end!
``````
1. For this file, how many total calls to `malloc` must have been made?
``````0 1 2 3 4 5 6 7 8 9
``````

As we form our hash table, we have been using 2 calls to `malloc`, one for the structure itself and one for the internal table. Then we have two (optional, since we could have used arrays on the stack) allocations for `word` and `last_word`. Most importantly, we have the bigrams that need to be put into the hash table. Whether these are malloced when we form the bigram or when we put it into the hash table, we need to have a call for `malloc` for each unique bigram so that the hash table can keep track of them. In the file example, there are exactly 9 bigrams and they are all unique, so we would have a total of 2+2+9=13 calls to `malloc`.

1. For this file, at the end of the program, how many more calls to `malloc` need to have been made than to `free`? In other words, how many blocks of memory do we need to still have accessible?
``````0 1 2 3 4 5 6 7 8 9
``````

The only real difference here is that it would be okay for `word` and `last_word` to be freed by the end of the program. In the end, our valid hash table must still have the 9 bigrams and the 2 hash table allocations for 11 total.

1. And for this file?
``````0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
``````

This file has a total of 19 bigrams, of which 9 are duplicates. We have one new bigram: "9 0". The hash table has no way of storing the duplicate bigrams, so they should all get freed at some point. We should have a total of 12 outstanding allocations left, just one more for the one new bigram!