18
$\begingroup$

I'm writing a small library for sparse matrix computations as a way to teach myself to make the best use of object-oriented programming. I've worked really hard on having a nice object model, where the parts (sparse matrices and the graphs which describe their connectivity structure) are very loosely coupled. In my own view, the code is much more extensible and maintainable for it.

However, it's also somewhat slower than if I had used a blunt approach. In order to test the tradeoffs of having this object model, I wrote a new sparse matrix type which broke the encapsulation of the underlying graph to see how much faster that would run.

At first, it looked pretty bleak; the code I was once proud of ran 60% slower than a version without any elegant software design. But, I was able to make a few low-level optimizations -- inlining a function and changing a loop a tiny bit -- without changing the API at all. With those changes, it's now only 20% slower than the competition.

Which brings me to my question: How much of a performance loss should I accept if it means I have a nice object model?

Improve this question
$\endgroup$
5
  • $\begingroup$ Which sparse matrix operation were you measuring? $\endgroup$
    – Bill Barth
    Commented Jun 10, 2014 at 2:34
  • $\begingroup$ Matrix-vector multiply. The matrices ranged in size from $n = 1024,...,16384$. I made them the graph Laplacians for Erdos-Renyi random graphs with average degree $d = \log_2n$. Also, the 20% figure gets worse on some machines, so now I'm more inclined to toss the whole thing out. Deep sigh $\endgroup$
    – Daniel Shapero
    Commented Jun 10, 2014 at 3:20
  • 3
    $\begingroup$ What programming language are you using? Typically something like C++ will let you get away with elegant(ish) designs at a low (or nonexistant) cost. In other languages without meta-programming (Java, Fortran, etc) a 20% cost seems reasonable. $\endgroup$
    – LKlevin
    Commented Jun 10, 2014 at 9:31
  • $\begingroup$ Can you show us your code? What language did you use? What compiler and compilation flags? Did you find precisely where the performance hit comes from? How did you make sure you found the right reason? What profiler did you use, and how did you use it? Are you certain that the nice object model is not implemented inefficiently? 20% is small enough that you need to collect a lot of data and have a detailed analysis before saying it's definitely due to the design, rather than, say, inferior implementation, or some other coding issues. $\endgroup$
    – Kirill
    Commented Jun 11, 2014 at 20:00
  • $\begingroup$ Short side-note: everyone seems to publicly praise good design over pure performance (with very valid reasons, of course). But then, why is so much real world code really, really unmaintainable? Are all code slobs feeling guilty and thus publicly silent? $\endgroup$
    – AlexE
    Commented Aug 12, 2014 at 6:53

5 Answers 5

Reset to default
9
$\begingroup$

Very few scientific software developers understand good principles of design, so I apologize if this answer is a bit long-winded. From a software engineering perspective, the goal of the scientific software developer is to design a solution that satisfies a set of constraints that are often conflicting.

Here are some typical examples of these constraints, as might be applied to the design of your sparse matrix library:

  • Completed in one month
  • Runs correctly on your laptop and several workstations
  • Runs efficiently

Scientists are gradually paying more attention to some other common requirements from software engineering:

  • Documentation (User guide, tutorial, code commenting)
  • Maintainability (version control, testing, modular design)
  • Reusability (modular design, "flexibility")

You might need more or less of one of these requirements. If you're trying to win a Gordon Bell prize for performance, then even fractions of a percent are relevant, and few of the judges will be evaluating the quality of your code (so long as you can convince them it's right). If you're trying to justify running this code on a shared resource such as a cluster or a supercomputer, frequently you have to defend claims about the performance of your code, but these are rarely very stringent. If you're trying to publish a paper in a journal describing the performance gains of your approach, then you need to legitimately be faster than your competitors, and 20% performance is a trade-off I would gladly make for better maintainability and reusability.

Coming back to your question, "good design", granted enough development time, should never sacrifice performance. If the objective is to make code that runs as fast as possible, then the code should be designed around those constraints. You might use techniques such as code generation, inline assembly, or take advantage of highly-tuned libraries to help you solve your problem.

But what if you don't have enough development time? What's good enough? Well, it depends, and nobody is going to be able to give you a good answer to this question without more context.

FWIW: If you really are interested in writing high-performance sparse matrix kernels, you should be comparing against an optimized PETSc install and working with their team if you are beating them, they'd be happy to incorporate tuned kernels to the library.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm curious about code generators -- I think they might be useful to me but I'm concerned they'll be hard to maintain. I know Java programmers use them a lot but they're often tailored to generate code for specific applications. Do you know of any scientific codes that use them? $\endgroup$
    – Daniel Shapero
    Commented Jun 13, 2014 at 18:25
  • $\begingroup$ ATLAS, FFTW, Spiral, OSKI, Ignition, stencil_codegen, to name several. It's not publicly advertised, but I wouldn't be surprised if several of the important kernels in MKL and ESSL are generated this way. Writing maintainable kernel generation code would be an interesting follow-up question. I have experience in this, but I wouldn't consider myself an authority. $\endgroup$
    – Aron Ahmadia
    Commented Jun 13, 2014 at 21:57
14
$\begingroup$

It's a question on what you spend your time on. For most of us, we spend 3/4 of the time programming and 1/4 of the time waiting for results. (Your numbers may vary, but I think the number is not completely without merits.) So, if you have a design that allowed you to program twice as fast (3/4 of a time unit instead of 1.5 time units), then you can can take a 300% hit in performance (from 1/4 to 1 time unit) and you still come out ahead in terms of real time spent on solving the problem.

On the other hand, if you're doing heavy duty computations, your calculations may look differently and you may want to spend more time optimizing your code.

To me, 20% seems like a fairly good trade-off if you end up being more productive.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Good answer, I'd also add the importance where performance matters. A given scientific code isn't doing solely matrix multiplication; if 20% of your runtime is in matrix multiplication, a 20% performance hit there is only a 4% difference overall, and I'd gladly take that in exchange for an easier-to-use library. $\endgroup$
    – Aurelius
    Commented Jun 11, 2014 at 14:44
  • 2
    $\begingroup$ And a better written library means less bugs, so that you waist less time waiting for incorrect results. $\endgroup$
    – Davidmh
    Commented Jun 15, 2014 at 18:11
4
$\begingroup$

IMHO a penalty of up to 50% (due to whatever reason) is not that bad.

In fact I have seen a 0-30% difference in performance just based on the type of compiler. This is for PETSc's sparse MatMult routine on matrices arising from low order FE discretizations.

Improve this answer
$\endgroup$
1
$\begingroup$

The software design won't automagically improve over time. The performance will. You will get the 20% back with your next CPU. Besides, good software design will make it easier to extend or improve the library in the future.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I don't think that this answer the question. $\endgroup$
    – nicoguaro ♦
    Commented Aug 12, 2014 at 12:45
0
$\begingroup$

A general principle is to go for good design first and then optimize on performance only if needed. Use-cases where a 20% performance gain is really needed are likely to be rather rare, if they come up at all.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.