Code. Photos. Excerpts from the life of an engineer.
Today was another momentous day in my physics career: the last lecture, the last discussion, the last quiz, and the last time I have to breathe inside of the Loomis Laboratory of Physics. Because of this, I decided to take some pictures during the day.
Just before the start of my last lecture in physics. This lecture was covering quantum periodic lattices.
After a full day in Loomis, I left the building for the last time (hopefully) in my life.
Today we knocked off two physics events that I will never have to do again! The first of those are the labs. My last lab was this morning at 8:00, and I took a few pictures to celebrate this momentous occasion.
Our lab room in Loomis.
Starting the last page of the lab!
My lab partner Steve doing some calculations.
Check, check, and check!
Today was also big news because I finished the last physics homework I’ll ever have to do:
I’m sorry, I realize that sounds like a really morbid title, but it’s kind of honest. So this Quantum Physics class I am taking has been the bane of my existence this semester. Physics is not really my thing. The other class this reminds me of is when I took Chemistry, that was also a horrendous subject (but I am thankful to those of you who like it). Today in physics lecture, I heard the impossible words come out of professor: “Today, we are going to combine our quantum physics knowledge to analyze and understand the intrinsic behaviors of chemistry!” I was astonished… physics is bad enough, but physics and chemistry in the same class? Let’s just say he lost me in the first like 2 minutes.
But fear not, with only 5 days left in physics, the great news is that every physics event from here on out will be the last time I ever have to do it: the last lecture, the last lab, the last homework, the last discussion section, and by golly the last exam.
Today I had the distinct privilege of dining with the parents of one of my good friends down here at college. I must say, there is not much better than a good meal with good people. Christian and his family (dad, mom, sister), Brett, Leman, and I arrived to eat at Olive Garden around 12:30. After much conversation, bread-sticks, salad, chicken parmesan, and Mousse cake, we departed at 3:30. Wow, time really flies when you’re having fun!
The gang (left to right): Christian, Christian’s mom, Christian’s sister, Brett, Leman, and Christian’s dad.
Christian’s dad showing off the bill he’s about to pay. Thanks for the meal!
I just finished implementing an autorelease pool opaque type for the MPRuntime, and to be honest, it’s pretty sweet. Basically an autorelease pool is a list that you put object pointers in, and then when you are done with the pool and you release it, it releases all of the objects in the pool. This can greatly reduce code size and also delay calling expensive memory free calls until a single moment.
Non-autorelease pool way:
Below is the old code for creating an array, and then adding 100 integers to it.
// Create an array and add a bunch of integers to it.
MPArrayRef array = MPArrayCreate(&kMPTypeArrayCallbacks);
for (unsigned i = 0; i < 100; i++)
{
MPNumberRef num = MPNumberCreateWithUnsigned(i);
MPArrayAppendValue(array, num);
MPRelease(num);
}
// Release our array.
MPRelease(array);
As you can see, it’s quite a hassle to keep the pointer around so you can call release on it. The example above isn’t the greatest because there are no like nested function calls and such, but just imagine magnifying the number of MPRelease statements and how many pointers you would have to keep around. So instead, as in the example below, you can simply autorelease the object so you don’t have to keep that pointer around, and you can send created objects directly in as arguments to function calls and what not.
Autorelease pool way:
// Create the pool.
MPAutoreleasePoolRef pool = MPAutoreleasePoolCreate(0);
// Create an array and add a bunch of integers to it.
MPArrayRef array = MPAutorelease(MPArrayCreate(&kMPTypeArrayCallbacks));
for (unsigned i = 0; i < 100; i++)
MPArrayAppendValue(array, MPAutorelease(MPNumberCreateWithUnsigned(i)));
// Release the pool, thus draining it.
MPRelease(pool);
Now that’s what I call sweet!
The files on the MPRuntime page contain the autorelease pool.
For an MP for class, I needed a data structure. I thought to myself, well, how would it be done at Apple? CoreFoundation. So I dug in and really tried to understand the CoreFoundation framework, and then implemented by own mini-version with many of the same paradigms. The system I came up with was the MPRuntime.
Here’s how it’s described on the MPRuntime page and in the header:
The MPRuntime API provides a set of opaque data types written in procedural C. The types are meant to make creating collections (such as lists and queues) as well as your own types much easier. The runtime presents a memory model that aids in preventing leakage, and takes after the paradigms of Apple’s CoreFoundation framework.
It should be noted that as of right now, the only opaque types implemented in the runtime include the runtime base (allocators, runtime instances), in addition to a strong array type and a number type for dealing with numbers. As more types become available, read their individual descriptions for usage.
Memory management with MPRuntime is done using reference counting. For every function that returns an object that has “Create” in the name, the object returned should be sent to MPRelease when you are done with the object. Similarly, if you want to keep an object around, you can call MPRetain to increase the retain count by one. You can read more about this at the following URL: http://en.wikipedia.org/wiki/Reference_counting.
Go ahead, download it and give it a try! See how easy data structures in C can really be.
That’s right, this morning, I actually ate breakfast. For those of you who know me, you will realize the extreme rarity of the situation. Usually I don’t like breakfast, partly a combination of time, the menu, and getting sick afterwards. However, this morning, I ate breakfast later in the morning, and so my stomach took it quite well. The menu consisted of:
Believe, I know it’s the worst meal in the world, but hey, it’s Bromley, and it’s the best I can do. At least I ate breakfast.
I just made some tweaks to the combsort. Basically, my version will now sort over a range of the array. You give it a start index, and then you give it how many integers from that index (including that index) you want to sort. The new code looks something like this:
void combsort_ranged(int * input, unsigned start, unsigned len, int (*comparison)(int *s0, int *s1))
{
unsigned end = start + len;
unsigned gap = len;
unsigned int swaps = 0xFFFF;
while(gap > 1 || swaps != 0)
{
if (gap > 1)
{
gap /= 1.3;
if (gap == 10 || gap == 9)
gap = 11;
}
unsigned i = start;
swaps = 0;
while (i + gap < end)
{
if (comparison(&(input[i]), &(input[i + gap])) > 0)
{
// Swap input[i] and input[i + gap]
int temp = input[i];
input[i] = input[i + gap];
input[i + gap] = temp;
swaps = 1;
}
i++;
}
}
}
When I wrote my CombSort algorithm yesterday, I started running into problems with arrays of small sizes. For example, the array {9, 2, 7, 4} would sort to {4, 2, 7, 9}. And then I realized, every time the last floor(count/1.3) elements failed comparison (meaning that they were already sorted), then the algorithm exited, leaving the middle of the array unsorted. With arrays of thousands or millions of integers, this was not a problem since the probability of this was miniscule. But, as the array size got smaller, this possibility rapidly increased, especially if the range of numbers was also decreased.
However, I just found my logic error, which occurred when testing to see if the algorithm should continue. I was reading that the algorithm should always run with a gap size of 1 (to ensure that it is sorted), even if the last pass didn’t sort anything. The condition for continuing should be if the gap is greater than one or the previous pass did not sort anything. Therefore, my original logic for testing this was flawed since it was the logical inverse.
The code should be:
while(gap > 1 || swaps != 0)
I have updated the original post to reflect this.
As I was working today on an MP, I needed a sorting algorithm that would work well with linked lists. For those of you who have ever written a linked list data structure of some kind, you will know that splitting and reallocated buffers and such is a pain. Sorting algorithms such as mergesort, heapsort, and quicksort use those kinds of techniques, making them very hard to implement on a linked list.
“But…”, you say, “mergesort and heapsort and quicksort all give us really good running times and memory usage!” Well my friends, do not fear, for there is another sorting algorithm I had never heard of until today: combsort. The idea of combsort is similar to that of bubblesort: going through the buffer linearly as many times as need, and the running comparisons on particular elements. No reallocation is done, no splitting, just the exchange of elements.
Yet again, bubblesort falls very short of the O(nlogn) running time of quick/merge/heapsort. But amazingly enough, combsort also runs in O(nlogn) as well! This makes combsort an extremely attractive option for a number of reasons:
Here is the C code for running combsort:
void combsort(int * input, unsigned count, int (*comparison)(int *s0, int *s1))
{
unsigned gap = count;
unsigned int swaps = 0xFFFF;
while(gap > 1 || swaps != 0)
{
if (gap > 1)
{
gap /= 1.3; // Funky magic number
if (gap == 10 || gap == 9)
gap = 11;
}
unsigned i = 0;
swaps = 0;
while (i + gap < count)
{
if (comparison(&(input[i]), &(input[i + gap])) > 0)
{
// Swap input[i] and input[i + gap]
int temp = input[i];
input[i] = input[i + gap];
input[i + gap] = temp;
swaps = 1;
}
i++;
}
}
}
How does Combsort perform?:
When sorting the same buffer of 10,000,000 integers, I got the following average times for different sorting algorithms.
BubbleSort > 24300.000 s // Or about 6.75 hours. HeapSort 14.518 s CombSort 11.189 s MergeSort 5.789 s QuickSort 4.497 s
So as you can see, combsort performs pretty dang well.
Conclusion:
Basically, I love combsort and I intend on making it my choice sorting algorithm for linked list structures, or any other structures where I don’t want to have to allocate some memory. To read more about combsort, check out its Wikipedia page.