Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

A lot of numerical algorithms (integration, differentiation, interpolation, special functions, etc.) are available in scientific computation libraries like GSL. But I often see code with "hand-rolled" implementations of these functions. For small programs which are not necessarily intended for public distribution, is it common practice among computational scientists to just implement numerical algorithms yourself (by which I mean copying or transcribing from a website, Numerical Recipes, or similar) when you need them? If so, is there a particular reason to avoid linking to something like GSL, or is it just more "tradition" than anything else?

I ask because I'm a big fan of code reuse, which would suggest that I should try to use existing implementations when possible. But I'm curious whether there are reasons that principle is less valuable in scientific computation than in general programming.


Forgot to mention: I'm specifically asking about C and C++, as opposed to languages like Python where there is a clear benefit (speed of execution) to using a library.

share|improve this question
9  
On one hand, you wouldn't want to reinvent the wheel. On the other hand, the best way to understand an algorithm (and by extension, easily diagnosing cases where the algorithm fails spectacularly) is to attempt coding an implementation yourself. –  J. M. Dec 2 '11 at 2:00
1  
Do you reprove every theorem you come across? Maybe you give it a shot and play around with some baby cases, but unless it's the focus of your research you probably accept it and move on with life. –  dls Dec 14 '11 at 20:07
    
Physicists are not programmers and they are not used to dealing with other people's code (reading it or fixing it). When they do have to use others' code, it's often not very well written or well commented code written by other physicists, again adding to the idea that it's better to re-write it than re-use it. This is true at least in some fields/communities, but attitudes are changing among younger people. It's not all bad though, think of the bad CS student's attitude who can't do something if he can't find an easy enough library for it. –  Szabolcs May 14 '13 at 14:28
add comment

14 Answers

up vote 33 down vote accepted

I used to implement everything myself, but lately have begun using libraries much more. I think there are several very important advantages of using a library, beyond just the issue of whether you have to write a routine yourself or not. If you use a library, you get

  • Code that has been tested by hundreds/thousands/more users
  • Code that will continue to be updated and improved in the future, without any work on your part
  • Optimized code that is more efficient and perhaps more scalable than what you would write in a first attempt
  • Depending on the library, by establishing an interface to it in your code you may get access to many algorithms that you currently don't use but may want to in the future

In the last bullet point above, I'm thinking of large libraries like Trilinos or PETSc. I can reinforce this with a couple of concrete personal examples in development of PyClaw. Although it would have been straightforward to parallelize Clawpack with MPI calls, we chose to use PETSc. This allowed us to limit the paralle code in the package to less than 300 lines of Python, but even better, by putting our data in PETSc's format we gained immediate access to PETSc's implicit solvers, enabling current work on an implicit solver in PyClaw. As a second example, PyClaw initially included hand-code fifth-order WENO reconstruction, but we eventually decided to rely on the PyWENO package for this. This was a huge gain, since PyWENO can automatically generate WENO routines of any order in several languages.

Finally, if you use libraries, you can contribute back by developing improvements or finding bugs, which will benefit many other people, whereas debugging or improving your own code only benefits you.

share|improve this answer
    
+1 for your point on reliability (that I forgot). –  PhDP Dec 2 '11 at 5:23
3  
"you can contribute back by developing improvements or finding bugs, which will benefit many other people." - that would satisfy both the "tinkering/learning" urge and the laziness (not having to do things that were already done). :) –  J. M. Dec 2 '11 at 5:24
add comment

There is substantial programmer overhead involved in linking to a library function, especially if that library is new to the programmer. It is often simpler to just rewrite simple algorithms rather than figure out the specifics of a particular library. As the algorithms become more complex this behavior switches.

Python has excelled at reducing this overhead with tools like pip/easy_install and a uniform data structure interface (i.e. every library seems to take and produce a numpy array).

share|improve this answer
add comment

One of the projects I'm involved in right now is writing a flexible simulation and analysis package for a class of particle physics detectors. One of the goals of this project is to provide the code base to be used in these things for decades to come.

At this point point we already have two dozen dependencies, making the build process such a nightmare that it has spun off a separate project managed out of the Fermilab computing center just to provide a reliable tool-chain.

Now imagine that you encounter a need for some tool that isn't in that tool-chain (happened to me just last month). You have three choices

  1. Roll you own. With all the risks and hassles that involves.
  2. Scrape some code out of a library somewhere and include it directing in The Project. Meaning that you have to take on maintenance going forward, and that you'll have to understand someone else's code when that happens.
  3. Go to the people who maintain the tool-chain, beg them for what you need and then wait for a release cycle to get it. These guys are pretty responsive, but you have to make the case for it without working code or after you've done (1) or (2).

It's very easy to choose (1). Maybe too easy.

share|improve this answer
    
Yes, added dependencies are a significant drawback of using libraries. –  David Ketcheson Dec 4 '11 at 6:56
    
Dependencies is the big drawback in my mind as well –  Fomite Dec 7 '11 at 15:03
1  
It's possible that my answer is putting too much weight on the fact of dependencies, and not enough on the bureaucratic process of getting dependencies approved ad installed in large projects. –  dmckee Dec 7 '11 at 18:37
add comment

I think it is quite common, with some algorithms more likely to be re-implemented than others.

There's a tricky trade-off between how annoying a library is to install, how hard it is to implement the algorithm yourself, how hard it is to optimize it, and how well the library fits your needs. Also, sometimes using a library is just overkill: I used the slow bisection algorithm in one of my programs because I called it only a few times and I didn't want to add a library just for that.

Is it easy for you to write a well-optimized version? If it is, you might be better off doing it. You're going to get exactly what you need and you won't depend on anyone's work. But of course you really need to know what you're doing: even simple algorithms can be tricky to implement.

I would be curious to see a study on this, but from my biased perspective, scientists often use libraries for linear algebra and random number generators, with most of the remaining code being homemade.

share|improve this answer
8  
"But of course you really need to know what you're doing: even simple algorithms can be tricky to implement." - this cannot be emphasized enough. –  J. M. Dec 2 '11 at 4:10
add comment

One answer is that there are so many slight variations to numerical code that it is really hard to encapsulate that in a library. Take this in comparison to web software, which is often easy to install and has a clear set of inputs and outputs. I think more common is people grabbing a framework, or big library that acts like a framework (Trilinos/PETSc), and using that ecosystem to get the benefits of using community codes.

share|improve this answer
add comment

I think that implementing an algorithm instead of using a library can sometimes give a better understanding and control of the model. When I am coding some program for scientific computations, it's important for me to understand what I am doing. Implementing the important algorithms helps me to get a better knowledge of the problem and achieve better control of it.

On the other hand, sometimes it's not a trivial task to select a library that is needed for getting a solution, so it's better to search for already-implemented algorithms when you are sure what are you trying to achieve and why do you want it.

If the algorithms are complex, then coding them by hand gives you the opportunity to improve performance/quality of solution using task-specific features. And sometimes it is necessary to change the algorithm a bit, which is easier if you know the code that you wrote and you can edit it in the way you want.

share|improve this answer
1  
+1 for improving understanding. Though this is more an issue for your own algorithms that for a library routine. –  Faheem Mitha Dec 12 '11 at 22:14
add comment

Thinking back to my second-year mechanics course, it occurs to me that part of reason I have implemented my own versions of well-known algorithms is that I was taught to do it that way. I can't think of a single example where I was taught how to interface to and link in a library in my undergrad physics education. I do have a fond memory of seeing for the first time a list of coordinates of a spinning golf ball, having computed the solution of the coupled Newton equations in FORTRAN myself. There is a certain thrill and satisfaction (even pride) that comes from calculating things from scratch.

share|improve this answer
    
This is certainly a factor. And that focus on do it yourself is necessary for a part of the education of a computational scientist. The pure programmers get it knocked out of them at some point, but us science types may move right from that introductory classroom into a projected populated almost exclusively by other people who came along the same route. –  dmckee Jan 12 '12 at 3:41
add comment

I think one should use tested libraries as much as possible. Most people are not experts in numerical computing and probably will not be able to implement a solution as correctly and carefully as what's available in well-tested libraries. That said, however, it is sometimes the case that there are no available libraries that implement the combination of capabilities needed in a given application. I've seen this happen in the technical area in which I work; existing codes didn't solve all the cases, and someone ended up implementing a solver from scratch that did.

share|improve this answer
1  
If the library doesn't cover all your needs, I would recommend that you extend the library code and submit a patch. That way you will benefit many others with your work, and others will also test your code for you. Of course, this assumes that the library code was written in a sufficiently flexible way that it can be extended to meet your needs. –  David Ketcheson Dec 11 '11 at 5:16
    
I agree, that's a great solution, and something people should do if at all possible. –  mhucka Dec 11 '11 at 23:04
add comment

My 2 cents.

I think it is easier to write generally about this, rather than just about C/C++. First, libraries in languages like Python are not necessarily used to get a speed benefit, even if that is a consequence. I think @David covered the reasons pretty well.

Taking it from the top, the language implementation to some extent dictates what libraries you have access to. Commonly used languages in computational science include C, C++, Python, Perl, Java, Fortran, and R. Less common examples might be Ocaml and Common Lisp. Now, since most of these languages are written in C, they have a natural Foreign function interface to C. However, it is not so easy to call, say, a Perl library from Python or vice versa. So in practice people tend to either

  1. Use a library written in their implementation language, usally something that is part of the standard libraries, or otherwise widely available, or

  2. Call a C/C++ library through the languages FFI. This assumes that a wrapper does not already exist, since if it does, it is not easily distinguishable from (1).

(2) is usually harder, because you have to wrap the C/C++ function yourself. Also, you have to either bundle the library, or add an extra dependency. For that reason, people are more likely to use the builtin language libraries rather than use GSL for example, which is in C.

For very generic routines, say generating random samples from distributions, or basic numerical routines like quadrature of integrals, it is easy and common to reuse some library. As the functionality one is trying to implement becomes more complex, it becomes exponentially more unlikely that one is going to find the exact function one wants in another library, and even one does, one could spend lots of time searching and finally adapting the function as necessary (the code style/design could be a problem for example). And as discussed above, one has access to only a subset of the libraries out there. On the other hand, implementing an algorithm oneself if it is complex and not the main focus can be daunting, and of course one has to deal with those pesky speed issues.

So, this becomes an optimization problem in cost/benefit analysis. My experience is that even for comparatively standard techniques like MCMC, I usually wind up writing my own code, because it fits better with how I am designing the overall software.

Of course, even if you end up not using the code, it is possible to learn from other people's code. I don't know how often scientists actually bother to do this, though. My impression is that reading other people's code to learn is more a software engineer thing.

share|improve this answer
add comment

The fundamental problem is often with the interface between the application and the library. An application programmer has knowledge about the problem that is often lost when passing the problem (for example as a matrix) to a library. This knowledge is such that exploiting it more than offsets the benefits of using the highly optimized library. As a result, the application programmer "rolls" his/her own implementation that does exploit the knowledge.

Thus, a really good library needs for such knowledge to be passed from the application into the library, so that the library, too, can take advantage of it.

share|improve this answer
add comment

Before deciding whether or not to use libraries, I think you'd also want to figure out how much the use of a library will help your code. If you're going to be using a well-optimized library for a key computational kernel, then it's probably a lot more efficient than trying to write your own.

However, if you're writing a specialized routine that's only going to be called once during a program's execution, it may not be worth it to adapt your code to fit the framework required by a library.

(Another thing to think about: how much re-architecting will you need to do to take advantage of the library? Unless the man-hours you spend to fix the code are compensated for by corresponding gains in efficiency or numerical accuracy, it may not be worth it in the long run. Ideally, though, this is something you plan for when initially designing data structures and algorithms, so that the library's "flow" is taken into account from the ground up.)

share|improve this answer
add comment

In addition to all the things already said above, I will repeat my answer from the "Fortran vs C++" question: The most valuable asset a programmer has is her time. Yes, external dependencies are often awkward. But spending time to re-implement, debug and test algorithms that others have already implemented is almost always stupid, and the result will also rarely be as good as code that was written by experts on a particular topic. Re-use what others have done!

share|improve this answer
add comment

The group I work with uses libraries as much as possible. I'm one of the few programmers, and the rest of the folks picked up programming on the job. They know enough of their own limitations to know where they shouldn't be dabbling. IMSL is the preferred library. Stuff like GSL would be forbidden due to licensing restrictions, even though this is a federal agency and we give our software away anyway.

share|improve this answer
add comment

"Re-use is primarily a social phenomenon. I can use someone else's software provided that

  1. it works
  2. it is comprehensible
  3. it can co-exist
  4. it is supported (or I'm willing to support it myself, mostly I'm not)
  5. it is economical
  6. I can find it.

" — B. Stroustrup, The C++ Programming Language 2 ed. (1991) p. 383.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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