[Xmonad] darcs patch: ShellPrompt.hs: a quick optimization of nub

[David Roundy]

On Tue, Oct 16, 2007 at 10:35:17AM +0200, Andrea Rossato wrote:
> On Mon, Oct 15, 2007 at 07:54:28PM -0400, gwern0 at gmail.com wrote:
> 
> > Mon Oct 15 19:48:50 EDT 2007  gwern0 at 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