Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>There's nothing better than a test, right? And the results are not unsurprising: for lists of random integers in range <code>[0 .. 1000000]</code>,</p> <pre><code>list size: 200000 ghc -O2 -fllvm -fllvm-O2 ──────── ──────── ──────── ──────── ──────── Data.List.sort 0.878969s 0.883219s 0.878106s 0.888758s Naïve.quicksort 0.711305s 0.870647s 0.845508s 0.919925s UArray_IO.quicksort 9.317783s 1.919583s 9.390687s 1.945072s Vector_Mutable.quicksort 1.48142s 0.823004s 1.526661s 0.806837s </code></pre> <p>Here, <code>Data.List.sort</code> is just what it is, <code>Naïve.quicksort</code> is the algorithm you quoted, <code>UArray_IO.quicksort</code> and <code>Vector_Mutable.quicksort</code> are taken from the question you linked to: <a href="https://stackoverflow.com/a/7833043/745903">klapaucius'</a> and <a href="https://stackoverflow.com/a/7719971/745903">Dan Burton's answer</a> <strong><em>which turn out to be very suboptimal performance-wise, see what better <a href="https://stackoverflow.com/a/11485331/745903">Daniel Fischer could do it</a></em></strong>, both wrapped so as to accept lists (not sure if I got this quite right):</p> <pre><code>quicksort :: [Int] -&gt; [Int] quicksort l = unsafePerformIO $ do let bounds = (0, length l) arr &lt;- newListArray bounds l :: IO (IOUArray Int Int) uncurry (qsort arr) bounds getElems arr </code></pre> <p>and</p> <pre><code>quicksort :: Ord a =&gt; [a] -&gt; [a] quicksort = toList . iqsort . fromList </code></pre> <p>respectively.</p> <p>As you can see, the naïve algorithm is not far behind the mutable solution with <code>Data.Vector</code> in terms of speed for sorting a list of random-generated integers, and the <code>IOUArray</code> is actually <em>much worse</em>. Test was carried out on an Intel i5 laptop running Ubuntu 11.10 x86-64.</p> <p><hr> <em>The following doesn't really make much sense considering that ɢᴏᴏᴅ mutable implementations are, after all, still well ahead of all those compared here.</em></p> <p>Note that this does not mean that a nice list-based program can always keep up with its mutably-implemented equivalents, but GHC sure does a great job at bringing the performance close. Also, it depends of course on the data: these are the times when the random-generated lists to sort contain values in between 0 and 1000 rather than 0 an 1000000 as above, i.e. with many duplicates:</p> <pre><code>list size: 200000 ghc -O2 -fllvm -fllvm-O2 ──────── ──────── ──────── ──────── ──────── Data.List.sort 0.864176s 0.882574s 0.850807s 0.857957s Naïve.quicksort 1.475362s 1.526076s 1.475557s 1.456759s UArray_IO.quicksort 24.405938s 5.255001s 23.561911s 5.207535s Vector_Mutable.quicksort 3.449168s 1.125788s 3.202925s 1.117741s </code></pre> <p>Not to speak of pre-sorted arrays.</p> <p>What's quite interesting, (becomes only apparent with really large sizes, which require rtsopts to increase the stack capacity), is how both mutable implementations become significantly <em>slower</em> with <code>-fllvm -O2</code>:</p> <pre><code>list size: 3⋅10⁶ ghc -O1 -fllvm-O1 -O2 -fllvm-O2 ──────── ──────── ──────── ──────── ──────── Data.List.sort 23.897897s 24.138117s 23.708218s 23.631968s Naïve.quicksort 17.068644s 19.547817s 17.640389s 18.113622s UArray_IO.quicksort 35.634132s 38.348955s 37.177606s 49.190503s Vector_Mutable.quicksort 17.286982s 17.251068s 17.361247s 36.840698s </code></pre> <p>It seems kind of logical to me that the immutable implementations fare better on llvm (doesn't it do everything immutably on some level?), though I don't understand why this only becomes apparent as a slowdown to the mutable versions at high optimisation and large data sizes.</p> <hr> <h2>Testing program:</h2> <pre><code>$ cat QSortPerform.hs module Main where import qualified Data.List(sort) import qualified Naïve import qualified UArray_IO import qualified Vector_Mutable import Control.Monad import System.Random import System.Environment sortAlgos :: [ (String, [Int]-&gt;[Int]) ] sortAlgos = [ ("Data.List.sort", Data.List.sort) , ("Naïve.quicksort", Naïve.quicksort) , ("UArray_IO.quicksort", UArray_IO.quicksort) , ("Vector_Mutable.quicksort", Vector_Mutable.quicksort) ] main = do args &lt;- getArgs when (length args /= 2) $ error "Need 2 arguments" let simSize = read $ args!!1 randArray &lt;- fmap (take simSize . randomRs(0,1000000)) getStdGen let sorted = case filter ((== args!!0) . fst) sortAlgos of [(_, algo)] -&gt; algo randArray _ -&gt; error $ "Argument must be one of " ++ show (map fst sortAlgos) putStr "First element: "; print $ sorted!!0 putStr "Middle element: "; print $ sorted!!(simSize`div`2) putStr "Last element: "; print $ sorted!!(simSize-1) </code></pre> <p>which takes the algorithm name and array size on command-line. Runtime comparison was done with this program:</p> <pre><code>$ cat PerformCompare.hs module Main where import System.Process import System.Exit import System.Environment import Data.Time.Clock import Data.List import Control.Monad import Text.PrettyPrint.Boxes compiler = "ghc" testProgram = "./QSortPerform" flagOpts = [[], ["-O2"], ["-fllvm"], ["-fllvm","-O2"]] algos = ["Data.List.sort","Naïve.quicksort","UArray_IO.quicksort","Vector_Mutable.quicksort"] main = do args &lt;- getArgs let testSize = case args of [numb] -&gt; read numb _ -&gt; 200000 results &lt;- forM flagOpts $ \flags -&gt; do compilerExitC &lt;- verboseSystem compiler $ testProgram : "-fforce-recomp" : flags when (compilerExitC /= ExitSuccess) . error $ "Compiler error \"" ++ show compilerExitC ++"\"" algoCompare &lt;- forM algos $ \algo -&gt; do startTime &lt;- getCurrentTime exitC &lt;- verboseSystem testProgram [algo, show testSize] endTime &lt;- getCurrentTime when (exitC /= ExitSuccess) . error $ "Program error \"" ++ show exitC ++"\"" return . text . show $ diffUTCTime endTime startTime return . vcat right $ text(concat flags) : text("────────") : algoCompare let table = hsep 2 bottom $ vcat left (map text $ ("list size: "++show testSize) : "────────" : algos ) : results printBox table verboseSystem :: String -&gt; [String] -&gt; IO ExitCode verboseSystem cmd args = do putStrLn . unwords $ cmd : args rawSystem cmd args </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POUsing vectors for performance improvement in Haskell
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USleftaroundabout
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POUsing vectors for performance improvement in Haskell
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COFantastic, thank you. I suspect the array implementation can be made much better. The answerer admits to directly porting code from Wikipedia, so it's probably not as efficient as it could be.
      singulars
      1. PO
      1. USPotato
    2. COI think so too, this is really just "let's port this C code to Haskell changing as little as possible", which can't be expected to be much good. However, the `Data.Array`s are generally said to be slower than `Vector`, so I doubt it could actually get much better than that. — Somewhere in the future, Data Parallel Haskell's `[: :]` will probably beat them all, including Fortran arrays...
      singulars
      1. PO
      1. USleftaroundabout
    3. CO@Potato Indeed, one can make much, much better array versions. And much much better vector versions. Both should beat the list versions by a huge margin.
      singulars
      1. PO
      1. USDaniel Fischer
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload