Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

repmat and replicating a Vector into a Matrix #152

Open
phunehehe opened this issue Sep 30, 2015 · 6 comments

Comments

@phunehehe
Copy link

commented Sep 30, 2015

If I'm benchmarking this right (which is an assumption because this is the first time I'm using criterion), when replicating a vector to create a matrix, using replicate and fromRows/fromColumns is always faster than using repmat and asRow/asColumn. The difference is huge with smaller vectors and smaller replications, but up to 10GB of memory, repmat still hasn't caught up.

Now, I imagine this is not really the main use of repmat, but what would you have done differently? Does it make sense to special case repmat for single row/column replication?

import           Criterion.Main        (bench, bgroup, defaultMain, nf, whnf)
import           Numeric.LinearAlgebra (Matrix, Vector, asRow, fromList,
                                        fromRows, repmat)

useRepmat :: Vector Double -> Int -> Matrix Double
useRepmat v i = repmat (asRow v) i 1

useReplicate :: Vector Double -> Int -> Matrix Double
useReplicate v i = fromRows $ replicate i v

main :: IO ()                    
main = defaultMain               
    [ bgroup "repmat"            
        [ bench "useRepmat whnf"    $ whnf (useRepmat v)    i   
        , bench "useReplicate whnf" $ whnf (useReplicate v) i
        , bench "useRepmat nf"      $ nf   (useRepmat v)    i   
        , bench "useReplicate nf"   $ nf   (useReplicate v) i
        ]                        
    ]                            
    where v = fromList [1..100000]                                                                                                                                                                           
          i = 10000              
benchmarking repmat/useRepmat whnf
time                 1.082 s    (1.039 s .. 1.123 s)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 1.075 s    (1.066 s .. 1.080 s)
std dev              8.008 ms   (0.0 s .. 8.299 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking repmat/useReplicate whnf
time                 1.036 s    (1.014 s .. 1.053 s)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 1.031 s    (1.029 s .. 1.033 s)
std dev              2.537 ms   (0.0 s .. 2.925 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking repmat/useRepmat nf
time                 1.068 s    (1.034 s .. 1.124 s)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 1.061 s    (1.052 s .. 1.067 s)
std dev              8.908 ms   (0.0 s .. 10.29 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking repmat/useReplicate nf
time                 813.0 ms   (447.5 ms .. 1.282 s)
                     0.949 R²   (0.949 R² .. 1.000 R²)
mean                 776.3 ms   (728.9 ms .. 868.8 ms)
std dev              80.11 ms   (0.0 s .. 80.77 ms)
variance introduced by outliers: 23% (moderately inflated)
@albertoruiz

This comment has been minimized.

Copy link
Collaborator

commented Sep 30, 2015

fromRows checks for equal (or unit) lengths and copies data into succesive memory regions. (fromCols is the same with a possible additional transposition.)

For simplicity repmat is currently defined using fromBlocks. This function checks that it has received an "autoconformable" rectangular list of lists: it expands single rows and columns to get consistent dimensions in all blocks (examples). Perhaps these checks may explain the difference.

In any case this implementation of repmat is inefficient since all blocks in the destination are equal and can be directly copied. I will try to get a better implementation using the recent inplace operations.

Thanks for testing!

@phunehehe

This comment has been minimized.

Copy link
Author

commented Sep 30, 2015

glad that made sense :)

@albertoruiz

This comment has been minimized.

Copy link
Collaborator

commented Oct 2, 2015

Can you benchmark the following implementation? It should not be much slower than fromRows.

https://github.com/albertoruiz/hmatrix/blob/test/examples/repmat.ipynb

@phunehehe

This comment has been minimized.

Copy link
Author

commented Oct 2, 2015

How did you know it won't beat fromRows :)
Here is the test https://gist.github.com/phunehehe/74f149b4012bcecf13e4
Things are a bit peculiar though:

  • For small matrices (100x100) rpmt is faster
  • For bigger ones (10000x10000) it ends up being slower
  • If I bump v to 100000, something even weirder happens: rpmt will use more memory than -M10g allows. Maybe this is an effect of things not being pure Haskell? I didn't let that test finish BTW.
@albertoruiz

This comment has been minimized.

Copy link
Collaborator

commented Oct 2, 2015

fromRows is just memcpy ;) And fromBlocks on a single vertical stack of matrices in row order only needs fromRows. A more interesting comparison would be repmat vs rpmt i j with j>1.

If the destination matrix fits in memory rpmt should finish without problems, it does not allocate any extra memory.

@phunehehe

This comment has been minimized.

Copy link
Author

commented Oct 3, 2015

You are right, rpmt is (almost?) always better than repmat when with j > 1, so we have a great improvement here already.
However, what I'm after right now is exactly the case where j = 1. I guess I'll just go with fromRows then. Thanks anyway :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.