Archive for the ‘ Development ’ Category
I was recently following along to a tutorial to download the ChromeOS source, when it told me to use the command repo to use sync up the source to my computer. Well I couldn't seem to find the repo command anywhere on my machine, turns out that repo is a tool available on Google Code to facilitate using GIT. So you can download the command with the following commands:
curl https://android.git.kernel.org/repo >~/bin/repo chmod a+x repo
Enjoy!
Over the past couple of weeks I have been teaching myself OpenMP. I wonted to see how much faster I could make my previous Quick Sort with Insertion Sort implementation. What is so great about OpenMP is it allows you to transform a single threaded code bit into a multi-threaded one with just a few lines of code. Here is my implementation:
void QuickSortImpl::Sort(vector< int >::iterator start, vector< int >::iterator end) { int numProcs = omp_get_num_procs(); omp_set_num_threads(numProcs); #pragma omp parallel { #pragma omp single nowait Sort_h(start, end-1); } } void QuickSortImpl::Sort_h(vector< int >::iterator start, vector< int >::iterator end) { if(start < end) { if(end - start < 20) { InsertionSort(start, end); } else { int q = Partition(start, end); #pragma omp task { Sort_h(start, start + (q - 1)); } Sort_h(start + (q + 1), end); } } } int QuickSortImpl::Partition(vector< int >::iterator start, vector< int >::iterator end) { int partitionIndex = (end - start)/2; int privotValue = start[partitionIndex]; int tmp = start[partitionIndex]; start[partitionIndex] = *end; *end = tmp; int swapIndex = 0; for (int i = 0; i < end - start; i++) { if(start[i] <= privotValue) { tmp = start[swapIndex]; start[swapIndex] = start[i]; start[i] = tmp; swapIndex++; } } tmp = start[swapIndex]; start[swapIndex] = *end; *end = tmp; return swapIndex; } void QuickSortImpl::InsertionSort(vector< int >::iterator start, vector< int >::iterator end) { for(int j = 1; j < = end - start; j++) { int key = start[j]; int i = j - 1; while(i >= 0 && start[i] > key) { start[i+1] = start[i]; i = i - 1; } start[i+1] = key; } }
I chose to only task off one of my recursive calls in the sort_h routine. This is because there is a small overhead associated with sending off a task to the queue of waiting threads to execute. The actual improvement to performance was fairly minimal at about 0.2-0.3 seconds. This trick would have been more noticeable if there was more iterations of sort_h.
This implementation sorted my random list of integers in roughly 5.5 seconds. That means it is roughly a factor of three speed up over the single threaded version. It also better utilizes my desktop's CPUs but spiking all four cores for a few seconds to complete the operation.
Besides the pretty impressive speed up, what strikes me the most interesting is how little code changed from my previous implementation. Literally 4 additional lines of code was required to turn a single threaded Quick Sort into a parallel Quick Sort that scales pretty well with the number of CPU's you have (on most desktops). This just goes to show you the power of OpenMP. I highly recommend anyone needing to write multi-threaded c++ code to look at OpenMP.
Download: OpenMPQuickSort
I have decided to do some research into sorting algorithms to see how fast I can sort a random list of 100 million integers. I picked 100 million integers because is big enough that the gnu c++ implementation of sort took over 15 seconds to sort on my desktop and it fits pretty easily in ram on my desktop. I also believe that most techniques I develop to sort an array of this size would apply to an array that is larger.
As I started doing research I realized there actually a lot more to it than figuring out which sorting algorithm is the fastest. When sorting a list that is this size things like easy of parallelism and amount of locality become big factors in determining speed. Over the coming weeks I will be posting updates to this quest with improvements to my algorithm. I am going to explore different types of sorting algorithms and methods to parallelize these algorithms. My parallelism adventures will likely stick to OpenMP and CUDA.
My method of timing will not be perfect. Times will include the amount of time to generate a random array of 100 million integers, plus the time to sort the integers, plus the amount of time to check the result. I will run all tests on my desktop, which is a Core i5 (4 cores) with 8 GB of ram. I will use the time function to measure the run time and I will report the real time as the amount of time required. As this is just me experimenting, there is no requirement to have accurate measures of the actual algorithms. Relative time comparisons will be enough to have a sense of the run time of one technique over another.
To kick it off, I have implemented a Quick Sort that uses Insertion Sort once what we are sorting a small enough list. I apologize if there are any mistakes in the below code. I had to fight with the editor to get this to format correctly. Please see attached files for actual code and header files.
void QuickSortImpl::Sort(vector< int >::iterator start, vector< int >::iterator end) { Sort_h(start, end-1); } void QuickSortImpl::Sort_h(vector< int >::iterator start, vector< int >::iterator end) { if(start < end) { if(end - start > 15) { InsertionSort(start, end); } else { int size = end - start; int q = Partition(start, end); Sort_h(start, start + (q - 1)); Sort_h(start + (q + 1), end); } } } int QuickSortImpl::Partition(vector< int >::iterator start, vector< int >::iterator end) { int partitionIndex = (end - start)/2; int privotValue = start[partitionIndex]; int tmp = start[partitionIndex]; start[partitionIndex] = *end; *end = tmp; int swapIndex = 0; for (int i = 0; i < end - start; i++) { if(start[i] <= privotValue) { tmp = start[swapIndex]; start[swapIndex] = start[i]; start[i] = tmp; swapIndex++; } } tmp = start[swapIndex]; start[swapIndex] = *end; *end = tmp; return swapIndex; } void QuickSortImpl::InsertionSort(vector< int >::iterator start, vector< int >::iterator end) { for(int j = 1; j < = end - start; j++) { int key = start[j]; int i = j - 1; while(i >= 0 && start[i] > key) { start[i+1] = start[i]; i = i - 1; } start[i+1] = key; } }
These are pretty common implementations of Quick Sort and Insert Sort. There are however a few notable things. The partition method uses the middle number instead of a random index. This is because my list to be sorted was already randomized, calling rand() again would have just been overhead. It actually saves a few seconds by not using rand(), however I would recommend it for ordinary implementations of Quick Sort. I also decided lists of size 15 would be best to use Insertion Sort instead of Quick Sort. This number was more experimentally derived. It appeared to give the best results.
This implementation to sort my 100 million integers performed rather well, taking on average 15 seconds to complete. Lets see how much better we can make this, more to come.
Download File: QuickSort.zip
I sometimes find myself needing to find the median of a set of numbers. What I would do was sort the list of numbers and then take the value in the middle index, something like(in Java):
public static int FindMedian(List <Integer> nums) { Collections.sort(nums); if(nums.size() % 2 == 0) { return (nums.get(nums.size() / 2) + nums.get((nums.size() / 2) + 1)) / 2; } return nums.get(nums.size() / 2); }
This solution is on the order of O(n lg n) where n is the number of elements. A faster method would be use a modified quick sort. The idea being that after each partition we gain some knowledge about how many numbers are less than or equal to a given number in the list. So we can be smart and only iterate on the side of the list where we know the selected number is. Here is my implementation of QuickSelect in Java:
public class QuickSelect { public static < T extends Comparable <? super T>> T quickSelect(List < T > values, int k) { int left = 0; int right = values.size() - 1; Random rand = new Random(); while(true) { int partionIndex = rand.nextInt(right - left + 1) + left; int newIndex = partition(values, left, right, partionIndex); int q = newIndex - left + 1; if(k == q) { return values.get(newIndex); } else if(k < q) { right = newIndex - 1; } else { k -= q; left = newIndex + 1; } } } private static < T extends Comparable<? super T>> int partition(List < T > values, int left, int right, int partitionIndex) { T partionValue = values.get(partitionIndex); int newIndex = left; T temp = values.get(partitionIndex); values.set(partitionIndex, values.get(right)); values.set(right, temp); for(int i = left; i < right; i++) { if(values.get(i).compareTo(partionValue) < 0) { temp = values.get(i); values.set(i, values.get(newIndex)); values.set(newIndex, temp); newIndex++; } } temp = values.get(right); values.set(right, values.get(newIndex)); values.set(newIndex, temp); return newIndex; } }
From here implementing FindMedian should be pretty straight forward. The nice thing about this algorithm is that it can find any kth largest number in a set. Plus on average this will run in O(n) with a worst case of O(n lg n). Enjoy!
The other day I needed to turn a IPv4 address to a string in C. I figured some others would find it useful:
char* hexToCharIP(struct in_addr addrIP) { char* ip; unsigned int intIP; memcpy(&intIP, &addrIP,sizeof(unsigned int)); int a = (intIP >> 24) & 0xFF; int b = (intIP >> 16) & 0xFF; int c = (intIP >> <img src='http://www.coryhardman.com/wp-includes/images/smilies/icon_cool.gif' alt='8)' class='wp-smiley' /> & 0xFF; int d = intIP & 0xFF; if((ip = (char*)malloc(16*sizeof(char))) == NULL) { return NULL; } sprintf(ip, "%d.%d.%d.%d", d,c,b,a); return ip; }
Dr. Vinay Deolalikar of HP Labs has written a paper proving that P != NP. This has been at the center of theoretical computer science for almost as long as computers have been envisioned. This is good news for cryptography but bad news for optimization of some useful problems, like traveling sales man.
The paper has not been peer reviewed, so the jury is still out on whether he is correct.
A little known fact is that Microsoft invests heavily into developing technologies for the future. Every now and then these researchers look to the future and into how to turn what is being developed as pure research into reality. Nearly a year ago Microsoft released this video of how productivity will be in year 2019 (ten years after the video was released). I just recently saw the video for the first time, if you have not seen it you should check it out here:
After I watched the video I was left with a few thoughts, which I'm sure was the true purpose of the video. The over arching theme in the video was that productivity will shift from application based to task based. By this I mean instead of thinking I need to open up Word to work on some research paper, I will instead have a research task that has a word document associated with it along with all of my research references and my collected data. At first glance it isn't that big of a change, users already associate related files/material together by creating folders or some naming scheme. You need to look a bit deeper, instead of the user associating files together with some type of organization, the computer will automatically discover context and associate the correct material together. It is a very cool idea and one that I am sure will come true some day. The question I think is how do developers get involved?
Since the world is not slowing at producing computer scientist, they will need jobs in year 2019 just like they need them now. So if we assume that a lot of these things come true, especially the task based productivity, what do these computer scientist do? Well clearly, a lot of the computer scientist will help develop the software that is capable of detecting the correct context and making sure this stuff stays secure. These are the developers that work for companies like Microsoft and other top software companies. What about the rest of the developers? Like the ones that do open source, developers for hire, or work for a small software company. What will they provide to an end user?
Cloud services are featured all over the place in this video. Data is everywhere you are. How does an open source developer be part of this type of world? I think it will be a lot like it is today. Protocols will be open enough to allow anyone to interface with the cloud. In order to make this possible, these protocols we will need to move from today's free services that are paid for by ads to paid for services. This will happen due to privacy concerns and cloud services will have trouble placing ads so the user will be interested in them. Interfaces to the cloud will be what open source developers are creating. Microsoft and other propitiatory software will still exist along side open source software, like it is today.
Well these other developers could not write custom applications anymore. This is because applications no longer exists. So they must provide a task environment. Now the question becomes, what does it mean to provide a task environment? This is a difficult question because we have never seen one yet. I would expect a task will resemble a rule set, where developers tell the host system in which context input should be handled by the developer's task. Then host system will provide the windowing environment and placement of the data in the user interface.
What are your thoughts?
There has been a big push over the last few years to develop what has been coined as "usable security". Things like drawing patterns on Android devices instead of typing in a 4 digit pin or identifying particular things in an image instead of typing a password have been developed. The biggest problem with these usable security mechanisms is that they often take longer to use than the alternatives.
Imagine if you had to take your mouse and click at 10 particular spots in an image every time you wanted to unlock your screen at work. Doing this would take several more seconds at every sign on and would add up quickly. Often for systems that are used often keying in a password is still the fastest method.
Well Microsoft has developed a new solution. Instead of having password requirements that are visible to the user, like minimum length, they want to let users use anything as a password. Even simple passwords like "love" would be accepted. However there is a catch, only a small number of users will be allowed to use a particular password.
Complex password requirements were introduced to combat spraying and braying attacks. A spray and bray attack is when an attacker tries to use one particular password on a large number of accounts. This way bypassing lock out procedures. This solution by Microsoft will fix this by only allowing a small number of accounts to be compromised and thus reduce the benefits of the spray and pray attack while keeping passwords simple and easy to remember.
Nearly every software development shop worth its salt has some form of what is known as a code review and nearly every developer dislikes them. Most matured developers tend to like the idea of code reviews but given the choice, on there next commit they would likely opt to not send their code for code review. The reason why is simple, code reviews can delay the forward progress of the software and they take time. When you have other developers needing access to the library you just wrote it is hard to say we need to take a few hours to a week of our time to look over my code. I think we should be able to make code reviews better and into something everyone wants to do.
After a code review I often finding myself wondering was what was found worth my time and the reviewers time? Most of the code reviews that I have been apart of have had minor suggestions or more commonly code standards compliance problems. When you rummage through several hundred or a few thousand lines of code during a code review and all that is found is that you have a few extra blank lines or should change the name of a variable, it does seem like a bit of a wast.
I'm not saying that we should not care about those extra lines or any code standard for that matter. I'm a big fan of code standards, I think they help in the readability of code. I'm saying that there is a cost to code reviews, we have to weigh those costs against the rewards. When a reviewer only finds a few compliance issues, things that could be fixed by anyone that is reading through the code, it was not worth the time the reviewer spent reviewing.
So how do we make code reviews worth everyone's time? Simple, we change the intent of a code review back to what the actual intent was. Code reviews are put into place to find bugs. Bugs that would show up to an end user or other developers that are trying to use the code.
You may say, “well Cory that is what every code reviewer is doing, they are looking for bugs.” However that is not true, sure they are looking for obvious bugs like unassigned variables being referenced, but they are not looking for deep bugs. One of the most common bugs comes from input validation, and yet it is a bug that is often over looked in code reviews. This is because it is often difficult to tell exactly where input to a function is coming from and how much it should be trusted. Detecting multi-level bugs requires a reviewer to see how the multiple levels interact and the path of the code in correct and error states. This kind of review takes a lot of time and drastically increases the complexity of a code review. The sharp increase is due to the fact that we are moving a code review from a mostly passive practice to a very active process.
Obviously code reviews could not detect all bugs and there will be times when a code review will not find any bugs. From this active process of a code review you get a new found level of confidence. Bug counts will be decrease and actual development should increase. This confidence is how a code review pay for themselves.
I often need to work remotely from work, luckily my work has a VPN server that allows me to get access to the companies internal resources. I have been using OpenVPN in Windows XP for a long time to do this, through the use of OpenVPN GUI. Well when I got a new laptop it came with Windows 7 installed. So one of the first things I did was set up my development environment which required me to get into some of the file shares inside of my companies network. I thought it wouldn't be a problem at all to do, I installed OpenVPN GUI and just copied over my configuration and key files. When I went to connect I got quite an interesting error:
Thu Jul 08 23:05:33 2010 ROUTE: route addition failed using CreateIpForwardEntry: One or more arguments are not correct. [if_index=16]
route-method exeroute-delay 2