Why is kmeans so slow on high spec Ubuntu machine but not Windows?

Question

My Ubuntu machine's performance is terrible for R kmeans {stats}, whereas Windows 7 shows no problems.

X is a 5000 x 5 matrix (numerical variables).
k = 6

My desktop machine is an Intel Xeon CPU W3530 @ 2.80GHz x 8 (i.e., 8 cores) Dell Precision T3500, with Ubuntu 12.04.4 LTS (GNU/Linux 3.2.0-58-generic x86_64) with 24 GB RAM.

R version 3.0.2 (2013-09-25) -- "Frisbee Sailing" Copyright (C) 2013 The R Foundation for Statistical Computing Platform: x86_64-pc-linux-gnu (64-bit)

> system.time(X.km <- kmeans(X, centers=k, nstart=25))
   user  system elapsed
 49.763  52.347 103.426

Compared to a Windows 7 64-bit laptop with Intel Core i5-2430M @ 2.40GHz, 2 cores, 8 GB RAM, R 3.0.1, and the same data:

> system.time(X.km <- kmeans(X, centers=k, nstart=25))

   user  system elapsed
   0.36    0.00    0.37

Much, much faster. For nstart=1 the problem still exists, I just wanted to amplify the execution time.

Is there something obvious I'm missing?

Try it for yourselves, see what times you achieve:

set.seed(101)
k <- 6
n <- as.integer(10)
el.time <- vector(length=n)
X <- matrix(rnorm(25000, mean=0.5, sd=1), ncol=5)
for (i in 1:n) {  # sorry, not clever enough to vectorise
    el.time[i] <- system.time(kmeans(X, centers=k, nstart=i))[[3]]
}
print(el.time)
plot(el.time, type="b")

My results (ubuntu machine):

> print(el.time)  
  [1] 0.056 0.243 0.288 0.489 0.510 0.572 0.623 0.707 0.830 0.846

Windows machine:

> print(el.time)
 [1] 0.01 0.12 0.14 0.19 0.20 0.21 0.22 0.25 0.28 0.30

Punchboard

According to your #sorry comment: sapply(1:n, function(i) system.time(kmeans(X, centers=k, nstart=i))[[3]]) instead of for loop. Note that there won't be any performance boost, since this is essentially the same. – Disbelieve

Also, what are your results for Windows machine? My Windows timings are close to yours on Ubuntu. – Disbelieve

Thanks @tonytonov. I'll update with the Windows timings on Monday when back at my desk. – Punchboard

@adifferentben the timings on my Ubuntu 12.04 virtual machine are in the same order of magnitude as you show. I suspect your Ubuntu machine runs out of memory and starts swapping. That would definitely explain the difference. – Abbyabbye

@PaulHiemstra, these sorts of things confuse me... why is a 24GB machine running out of memory when an 8GB machine isn't? – Punchboard

@adifferentben I was just speculating, swapping might explain the huge performance difference. – Abbyabbye

I notice your ubuntu R is 3.0.2, while windows is 3.0.1. The kmeans function was updated for 3.0.2, and in my tests was about 20% slower than the previous version. That's not enough to explain the difference you're seeing, but I thought it was worth mentioning. – Tiga

@ping, I've now upgraded to 3.1.0 on Ubuntu, and timings are marginally faster, but only marginally. – Punchboard

@a-different-ben Yeah I'd assume (but haven't checked) that kmeans in 3.1.0 is the same as 3.0.2, to try the faster version you would downgrade to 3.0.1. Still wouldn't expect it to be enough to fix your problem though... – Tiga

Answer 1

Are you running Ubuntu in a Virtual Machine? If that were the case I could see the the results are much slower - Depending on how much memory, processors, diskspace was allocated for the VM. If it isn't running in a VM then the results are puzzling. I would want to see Performance counter for each of the runs (what is the cpu usage, memory usage, etc) on both systems when you run this? Otherwise, the only thing I could link of is that the code "fits" in the L1 cache of your windows system but doesn't in the Linux system. The Xeon has 8GB (L3?) Cache where the Core i5 only has 3MB - but I'm assuming that's L3. I don't know what the L1 and L2 cache structures look like.

Velodrome

No it's a disk-based install. I also have no idea of the caches, or even what they would mean to this problem! I think @Tiga has the best clue so far. I did update my installs recently, but I haven't been back to check this code yet. Will update it soon when back at work. – Punchboard

Answer 2

My guess is it's a BLAS issue. R might use the internal BLAS if compiled like that. In addition to this, different BLAS versions can show significant performance differences (openBLAS <> MKL).

Lamelliform