darcs patch: ShellPrompt.hs: a quick optimization of nub
Mon Oct 15 19:48:50 EDT 2007 gwern0@gmail.com * ShellPrompt.hs: a quick optimization of nub I saw some complaints about ShellPrompt being slow - and noticed it myself - and it seems ShellPrompt uses 'nub' in an awkward place to uniquefy input. Nub doesn't perform well on long lists, but I once ran into a similar problem and the suggested solution was something clever: convert to a Set and then back to a List. Sets can't have duplicate entries, and they uniquefy faster than nub. The price is that the output is not sorted the same as nub's output would be, but this is OK because the output of (toList . fromList) is immediately passed to 'sort' - which should then produce the same output for both versions. I haven't really tested this but on long directories this should help.
On Monday 15 October 2007 18:54:28 gwern0@gmail.com wrote:
Mon Oct 15 19:48:50 EDT 2007 gwern0@gmail.com * ShellPrompt.hs: a quick optimization of nub I saw some complaints about ShellPrompt being slow - and noticed it myself - and it seems ShellPrompt uses 'nub' in an awkward place to uniquefy input. Nub doesn't perform well on long lists, but I once ran into a similar problem and the suggested solution was something clever: convert to a Set and then back to a List. Sets can't have duplicate entries, and they uniquefy faster than nub. The price is that the output is not sorted the same as nub's output would be, but this is OK because the output of (toList . fromList) is immediately passed to 'sort' - which should then produce the same output for both versions. I haven't really tested this but on long directories this should help.
Applied.
On Mon, Oct 15, 2007 at 07:54:28PM -0400, gwern0@gmail.com wrote:
Mon Oct 15 19:48:50 EDT 2007 gwern0@gmail.com * ShellPrompt.hs: a quick optimization of nub I saw some complaints about ShellPrompt being slow - and noticed it myself - and it seems ShellPrompt uses 'nub' in an awkward place to uniquefy input. Nub doesn't perform well on long lists, but I once ran into a similar problem and the suggested solution was something clever: convert to a Set and then back to a List. Sets can't have duplicate entries, and they uniquefy faster than nub. The price is that the output is not sorted the same as nub's output would be, but this is OK because the output of (toList . fromList) is immediately passed to 'sort' - which should then produce the same output for both versions. I haven't really tested this but on long directories this should help.
Indeed the benchmarks I tried show that the problem was nub. Quite amazingly changing nub with toList . fromList means reducing cpu time of about 75%. With numb: time promptReadline /usr/bin/ 2878 real 0m8.504s user 0m7.559s sys 0m0.019s time promptGetDirCont /usr/bin/ 2878 real 0m8.429s user 0m7.554s sys 0m0.039s With toList . fromList: time promptReadlineSet /usr/bin/ 2878 real 0m0.110s user 0m0.082s sys 0m0.004s time promptGetDirContSet /usr/bin/ 2878 real 0m0.227s user 0m0.185s sys 0m0.022s It is true that ReadLine is twice quicker that getDirectoryContent but I would prefer not to rely on an external library for such an improvement. What do you think? Andrea
On Tue, Oct 16, 2007 at 10:35:17AM +0200, Andrea Rossato wrote:
On Mon, Oct 15, 2007 at 07:54:28PM -0400, gwern0@gmail.com wrote:
Mon Oct 15 19:48:50 EDT 2007 gwern0@gmail.com * ShellPrompt.hs: a quick optimization of nub I saw some complaints about ShellPrompt being slow - and noticed it myself - and it seems ShellPrompt uses 'nub' in an awkward place to uniquefy input. Nub doesn't perform well on long lists, but I once ran into a similar problem and the suggested solution was something clever: convert to a Set and then back to a List. Sets can't have duplicate entries, and they uniquefy faster than nub. The price is that the output is not sorted the same as nub's output would be, but this is OK because the output of (toList . fromList) is immediately passed to 'sort' - which should then produce the same output for both versions. I haven't really tested this but on long directories this should help.
Indeed the benchmarks I tried show that the problem was nub. Quite amazingly changing nub with toList . fromList means reducing cpu time of about 75%.
nub is a common source of slowness, because it's O(N^2). In darcs, we use a function nubsort, which first calls sort, and then removes duplicate entries (which is just the O(NlogN) cost of sort, plus O(N). I'd recommend this over the toList . fromList approach, although I've never compared timings, mostly because of simplicity: it's hard to imagine that you'll beat the efficiency of sort--particularly as you want the output sorted--and the rest is O(N), so it won't matter for large input.
It is true that ReadLine is twice quicker that getDirectoryContent but I would prefer not to rely on an external library for such an improvement. What do you think?
I'd vote for not depending on readline, if for no other reason, to avoid having to hack the xmonad.cabal file. -- David Roundy Department of Physics Oregon State University
participants (4)
-
Andrea Rossato -
David Roundy -
gwern0＠gmail.com -
Spencer Janssen