I used computer science at work and it was fun.
A coworker and I were talking just the other day about a situation where our code would need to enumerate every open file for a given process. We had a binary tree structure in memory that maintained the list for our process as well as the option of retrieving the information via '/proc'. Since we needed to touch every element in our tree in memory, that's easily identifiable as O(n), but what was unclear for our now group of four deliberators was whether the enumerating of the /proc/[pid]/fd file would be just as fast, faster, or slower. Ultimately, a couple of them settled on the fact that it would be the same speed since you still needed to enumerate every file descriptor, and it would be just as fast to make the system call to retrieve the proc info. I disagreed. My argument was that compute is always going to be faster than I/O, and even though it's a system call to a pseudo-filesystem, it makes sense to crawl the tree instead of getting it from proc. To prove my suspicion, I created the following experiment:
1. Run a program that opens and holds 2**x file descriptors.
2. Run a script to build a tree of 2**x levels in memory.
3. Using the same script, walk the tree using a depth first search. (Time this function)
4. Using the same script, attempt to read the list of FDs from /proc/[pid]/fd. (Time this function)
5. Compare the result of the function timers.
2. Run a script to build a tree of 2**x levels in memory.
3. Using the same script, walk the tree using a depth first search. (Time this function)
4. Using the same script, attempt to read the list of FDs from /proc/[pid]/fd. (Time this function)
5. Compare the result of the function timers.
Results: At 10 levels, the tree enumeration took 0 milliseconds, while the I/O required about 55 milliseconds to complete. When I increased the size of the tree to 16 levels, the time required to walk the structure increased to around 25 milliseconds. Compute was faster.
Notes:
1. This is not bleeding edge accurate. The python package 'psutil' is essentially a piece of middleware that could influence the time it takes to return the list of file descriptors, but I think still accurately simulates what enumerating the proc file would require.
2. The accuracy of the time.time() value used for the experiment is two decimal places on my test machine.
1. This is not bleeding edge accurate. The python package 'psutil' is essentially a piece of middleware that could influence the time it takes to return the list of file descriptors, but I think still accurately simulates what enumerating the proc file would require.
2. The accuracy of the time.time() value used for the experiment is two decimal places on my test machine.
You can find the experiment files HERE.
No comments:
Post a Comment