Skip to main content

Questions tagged [performance]

Questions about the execution speed and memory usage of algorithms, data structures, languages and libraries.

Filter by
Sorted by
Tagged with
68 votes
10 answers
16k views

What are some good strategies for improving the serial performance of my code?

I work in computational science, and as a result, I spend a non-trivial amount of my time trying to increase the scientific throughput of many codes, as well as understanding the efficiency of these ...
Aron Ahmadia's user avatar
  • 6,901
50 votes
4 answers
32k views

What makes Fortran fast?

Fortran has a special place in numerical programming. You can certainly make good and fast software in other languages, but Fortran keeps performing very well despite its age. Moreover, it's easier to ...
cauchi's user avatar
  • 887
48 votes
7 answers
6k views

Is algorithmic analysis by flop-counting obsolete?

In my numerical analysis courses, I learned to analyze the efficiency of algorithms by counting the number of floating-point operations (flops) they require, relative to the size of the problem. For ...
David Ketcheson's user avatar
40 votes
5 answers
35k views

How does the MATLAB backslash operator solve $Ax=b$ for square matrices?

I was comparing a few of my codes to "stock" MATLAB codes. I am surprised at the results. I ran a sample code (Sparse Matrix) ...
Inquest's user avatar
  • 3,384
33 votes
5 answers
16k views

Performance differences between ATLAS and MKL?

ATLAS is a free BLAS/LAPACK replacement that tunes itself to the machine when compiled. MKL is the commercial library shipped by Intel. Are these two libraries comparable when it comes to performance, ...
Stefano Borini's user avatar
31 votes
4 answers
2k views

What tools or approaches are available to speed up code written in Python?

Background: I think I might want to port some code that calculates matrix exponential-vector products using a Krylov subspace method from MATLAB to Python. (Specifically, Jitse Niesen's expmvp ...
Geoff Oxberry's user avatar
27 votes
1 answer
32k views

What is the preferred and efficient approach for interpolating multidimensional data?

What is the preferred and efficient approach for interpolating multidimensional data? Things I'm worried about: performance and memory for construction, single/batch evaluation handling dimensions ...
den.run.ai's user avatar
25 votes
8 answers
5k views

Is it possible for user written algorithms to outperform libraries' built-in optimized functions?

I've always had this question in mind (even if it may sound vague), but in my numerical analysis courses we've always learned how to analyze and optimize code. However, since most linear algebra ...
CynthiaZ1998's user avatar
25 votes
4 answers
3k views

When should I use C++ expression templates in computational science, and when should I *not* use them?

Suppose that I'm working on a scientific code in C++. In a recent discussion with a colleague, it was argued that expression templates could be a really bad thing, potentially making software ...
Geoff Oxberry's user avatar
24 votes
3 answers
21k views

Intel Fortran Compiler: tips on optimization at compilation

I will start with my personal experience in our lab. Back in the ifort 9 and 10 days, we used to be quite aggressive with the optimizations, compiling with -O3 and processor specific flags (-xW -xSSE4....
FrenchKheldar's user avatar
23 votes
3 answers
3k views

Can diagonal plus fixed symmetric linear systems be solved in quadratic time after precomputation?

Is there an $O(n^3+n^2 k)$ method to solve $k$ linear systems of the form $(D_i + A) x_i = b_i$ where $A$ is a fixed SPD matrix and $D_i$ are positive diagonal matrices? For example, if each $D_i$ is ...
Geoffrey Irving's user avatar
20 votes
1 answer
3k views

How does the performance of Python/Numpy array operations scale with increasing array dimensions?

How do Python/Numpy arrays scale with increasing array dimensions? This is based on some behaviour I noticed while benchmarking Python code for this question: How to express this complicated ...
Nat Wilson's user avatar
19 votes
6 answers
3k views

To what extent is generic and meta-programming using C++ templates useful in computational science?

The C++ language provides generic programming and metaprogramming through templates. These techniques have found their way into many large-scale scientific computing packages (e.g., MPQC, LAMMPS, CGAL,...
Deathbreath's user avatar
  • 1,032
18 votes
4 answers
5k views

Portable multicore/NUMA memory allocation/initialization best practices

When memory bandwidth limited computations are performed in shared memory environments (e.g. threaded via OpenMP, Pthreads, or TBB), there is a dilemma of how to ensure that the memory is correctly ...
Jed Brown's user avatar
  • 25.7k
16 votes
2 answers
2k views

Open source implementation of rational approximation to a function

I am looking for some open source implementation (any of Python, C, C++, Fortran is fine) of rational approximation to a function. Something along the article [1]. I give it a function and it gives me ...
Ondřej Čertík's user avatar
16 votes
3 answers
17k views

What is the fastest way to compute all eigenvalues of a very big and sparse adjacency matrix in python?

I'm trying to figure out if there is a faster way to compute all the eigenvalues and eigenvectors of a very big and sparse adjacency matrix than using scipy.sparse.linalg.eigsh As far as I know, this ...
Noam Peled's user avatar
15 votes
4 answers
409 views

How to deal with too much data?

Our plasma dynamics simulations often produce too much information. During the simulations we record various physical properties on a grid (x,y,z,t) that is as large as (8192x1024x1024x1500), for at ...
Yann's user avatar
  • 852
14 votes
3 answers
2k views

Comparison of iteration methods: number of iterations vs. cpu time

I am comparing two iterative methods for inverting random square matrices. Since the matrices are random, every test case takes both different amounts of iterations and different elapsed times. My ...
Srijan's user avatar
  • 365
13 votes
3 answers
1k views

Is there any benefit to compiling LAPACK from source versus installing the prebuilt package from Ubuntu?

I know that ATLAS is able to optimize itself for the machine it is compiled on and thus maximum benefits are found by compiling from source. Is there any benefit to compiling LAPACK from source? It ...
OSE's user avatar
  • 397
13 votes
4 answers
8k views

FLOP counting for library functions

When evaluating the number of FLOPs in a simple function, one can often just go down the expression tallying basic arithmetic operators. However, in the case of mathematical statements involving even ...
Peter Brune's user avatar
  • 1,675
13 votes
3 answers
37k views

How to properly calculate CPU and GPU FLOPS performance?

Problem I'm trying to calculate CPU / GPU FLOPS performance but I'm not sure if I'm doing it correctly. Let's say we have: A Kaby Lake CPU (clock: 2.8 GHz, cores: 4, threads: 8) A Pascal GPU (clock: ...
AlekseyHoffman's user avatar
13 votes
5 answers
2k views

Calculation of the sparsity structure for finite element matrices

Question: What methods are available to accurately and efficiently calculate the sparsity structure of a finite element matrix? Info: I'm working on a Poisson Pressure Equation solver, using Galerkin'...
John Edwardson's user avatar
13 votes
3 answers
421 views

In what application cases are additive preconditioning schemes superior to multiplicative ones?

In both domain decomposition (DD) and multigrid (MG) methods, one may compose the application of the block updates or coarse corrections as either additive or multiplicative. For pointwise solvers, ...
Peter Brune's user avatar
  • 1,675
12 votes
2 answers
1k views

Faster Logistic Function

I've noticed that a fairly significant number of cycles in one of my programs are being consumed by the logistic function: $$f(x)=\frac{1}{1+e^{-x}}$$ Is there a good approximation I can use to reduce ...
Richard's user avatar
  • 3,971
12 votes
3 answers
6k views

Memory usage in fortran when using an array of derived type with pointer

In this sample program I'm doing the same thing (at least I think so) in two different ways. I'm running this on my Linux pc and monitoring the memory usage with top. Using gfortran I find that in the ...
chris's user avatar
  • 1,045
12 votes
2 answers
12k views

Octave: calculate distance between two matrices of vectors

Suppose I have two matrices Nx2, Mx2 representing N, M 2d vectors respectively. Is there a simple and good way to calculate distances between each vector pair (n, m)? The easy but inefficient way is ...
Kelley van Evert's user avatar
11 votes
3 answers
3k views

What is the overhead in sparse matrix multiplication

Does matrix multiplication (both Mat*Mat, and Mat*Vec) scale with number of non-zeros, or with the size of the matrix? Or some combination of the two. What about with shape. For example, I have a ...
Andrew Spott's user avatar
  • 1,155
11 votes
1 answer
3k views

What is the state of the art algorithm for diagonalizing real symmetric matrices?

There are many methods for diagonalizing matrices, probably the most widely used is the combination of Householder transformations and the QR algorithm. Is there any superior method for diagonalizing ...
uLoop's user avatar
  • 213
11 votes
3 answers
314 views

How to implement efficient indexing function for two particle integrals <ij|kl>?

This is a simple symmetry enumeration problem. I give the full background here, but no knowledge of quantum chemistry is needed. The two particle integral $\langle ij|kl\rangle$ is: $$ \langle ...
Ondřej Čertík's user avatar
11 votes
1 answer
259 views

Statistical models for local memory/compute, network latency, and bandwidth jitter in HPC

Parallel computation is frequently modeled using a deterministic local rate of computation, latency overhead, and network bandwidth. In reality, these are spatially variable and non-deterministic. ...
Jed Brown's user avatar
  • 25.7k
10 votes
3 answers
6k views

MATLAB matrix multiplication (the best computational approach)

I have to make a coordinates transformation between two reference systems (axes). For that, three matrices ($3\times3$) have to be multiplied due to some intermediate axes being used. I have thought ...
julianfperez's user avatar
10 votes
3 answers
18k views

The real myth of GPU (specifically CUDA) really speed up FEM/CFD

Now I have been believing that FEM/CFD is supposed to be faster on a GPU unit - here I am using CUDA as solid example. However, I have not been able to find a convincing paper where the benchmark ...
Quang Thinh Ha's user avatar
10 votes
2 answers
368 views

What is the underlying structure of scientific code performance?

Consider two computers with different hardware and software configurations. When running the exact same serial Navier-Stokes code on each platform it takes x and y time to execute one iteration for ...
Isopycnal Oscillation's user avatar
10 votes
3 answers
8k views

Nvidia K20X vs GeForce Titan for GPGPU acceleration

Im trying to understand the difference between these two graphics cards for academic computing, specifically for the DGEMM component. If we look at the raw statistics, both have the same GK110 chip, ...
Ophion's user avatar
  • 153
10 votes
2 answers
9k views

Integer operations vs floating point operations

I have been working with an algorithm, which uses additions of floating point vectors, (sparse matrix of floats)x(dense vector of floats) dot products I recently found out that I can get the same ...
Dionysios Georgiadis's user avatar
10 votes
1 answer
3k views

Fortran 90/95: Deallocating variables

I understand the crucial importance of freeing memory when certain variables or arrays need to be reused later in the program, or may not be in use for a while. However, in my experience with ...
Salim's user avatar
  • 165
10 votes
4 answers
5k views

Are DAXPY, DCOPY, DSCAL overkills?

I have implemented CG in FORTRAN by linking it to Intel MKL. When there are statements like: (Refer Wikipedia) p=r; x=x+alpha*p r=r-alpha*Ap; or similar ...
Inquest's user avatar
  • 3,384
10 votes
1 answer
722 views

What is the impact of C++11 move semantics in the context of scientific computing?

C++11 introduces move semantics which can, for example, improve code performance in situations where C++03 would need to perform a copy construction or copy assignment. This article reports that ...
okmatija's user avatar
  • 505
10 votes
3 answers
276 views

Literature references for modeling current and future energy costs of floating-point operations and data transfers

I am searching for the most important literature and slide references for modeling current and future energy costs of floating-point operations and data transfers across the CPU, memory, network, and ...
9 votes
10 answers
5k views

Is it possible to optimise this integration code so that it runs faster?

...
user2970116's user avatar
9 votes
2 answers
2k views

Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?

I have a system of conductors for which there are two dense matrices of the (complex) mutual admittances, $Y_A$ and $Y_B$, which are symmetric. Then, an equivalent nodal admittance matrix $Y_N$ is ...
Pedro H. N. Vieira's user avatar
9 votes
1 answer
2k views

Increasing computational performance by using 16 bit numbers

I recently found the following article where it was stated that using 16 bit numbers can be used to increase the computational performance of AI applications. According to the article numbers above 16 ...
vydesaster's user avatar
9 votes
1 answer
1k views

Hardware performance, floating point functions

First of all, hope I've found the right forum for this question, if I haven't please pass me on to one which would fit better. Out of curiosity from an argument with someone who may or may not be more ...
mathreadler's user avatar
9 votes
3 answers
4k views

What is the fastest opensource implementation of Bessel functions computation?

I'm looking for an open-source (to use and learn from) software which computes Bessel functions of integer order of real argument to double precision the fastest among all such implementations. ...
Ruslan's user avatar
  • 204
9 votes
2 answers
472 views

How do Volkov and Demmel experimentally determine the latencies, line sizes, and page sizes of a GPU?

In "LU, QR and Cholesky Factorizations using Vector Capabilities of GPUs", by Vasily Volkov and James Demmel, there is an interesting way to interpret the latencies, line sizes, and page sizes of a ...
John Hoffman's user avatar
9 votes
2 answers
950 views

Which Sparse Matrix Solver Libraries can I run on Android?

The title says most of it. I'm looking for a lightweight and easy-to-use library that I can use for Android (NDK) projects. For dense stuff I like using Eigen but I haven't found many comprehensive (...
rsp1984's user avatar
  • 435
9 votes
2 answers
398 views

Fastest way to find eigenpairs of a small nonsymmetric matrix on a GPU in shared memory

I have a problem where I need to find all positive (as in the eigenvalue is positive) eigenpairs of a small (usually smaller than 60x60) nonsymmetric matrix. I can stop calculating when the eigenvalue ...
Kantoku's user avatar
  • 91
9 votes
2 answers
3k views

How do I compute the parallel overhead of a parallel code run on a single processor when no sequential code is available?

I'm profiling the performance of PETSc's linear solvers. As I understand it, $$\text{speedup}=\frac{\text{Sequential Time}}{\text{Parallel Time}}.$$ I know that running the parallel code on one ...
Paul's user avatar
  • 12k
8 votes
4 answers
390 views

(How) do you take into account memory fragmentation?

I use an example from finite element theory, but anybody who maintains a large datastructure and successively extends it will find something similar. Suppose I have an unstructured mesh of points and ...
shuhalo's user avatar
  • 3,670
8 votes
1 answer
3k views

What is the best way to multiply a diagonal matrix (in fortran)

What is the best way to compute: $$ Y = D X $$ where $D \in \mathbb{R}^{m\times m}$ is diagonal and $X \in \mathbb{C}^{m \times n}$ is general. I am mostly interested in these two cases: $m >> ...
Max Hutchinson's user avatar