1

Does it makes sense to implement your own version of data structures and algorithms in your language of choice even if they are already supported, knowing that care has been taking into tuning them for best possible performance?

Improve this question
4
  • Depends on the reason for doing so. There might be justification in a given situation. Far too general to say. Commented Sep 18, 2012 at 15:52
  • 4
    Maybe, maybe not. Depends on your reasons for reimplementing it. I would image there are usually circumstances under which one could make a good argument for reimplementing anything. Do you want specific examples? What's the real question? Commented Sep 18, 2012 at 15:53
  • @Patrick87 Examples are most welcome. Yes. Commented Sep 18, 2012 at 15:57
  • 3
    @saadtaame: what's the exact question? The answer to "does it always make sense to do this?" is "no", and the answer to "does it ever make sense to do this?" is "yes". Commented Sep 18, 2012 at 16:26

3 Answers 3

Reset to default
3

Sometimes - yes. You might need to optimise the data structure for your specific case, or give it some specific extra functionality.

A java example is apache Lucene (A mature, widely used Information Retrieval library). Although the Map<S,T> interface and implementations already exists - for performance issues, its usage is not good enough, since it boxes the int to an Integer, and a more optimized IntToIntMap was developed for this purpose, instead of using a Map<Integer,Integer>.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

That's kinda ignoring the "assuming the existing one is tuned for best performance" part of the question. I'm not saying it's a reasonable assumption, but it's there.
3

The question contains a false assumption, that there's such a thing as "best possible performance".

If the already-existing code was tuned for best possible performance with your particular usage patterns, then it would be impossible for you to improve on it in respect of performance, and attempting to do so would be futile.

However, it wasn't tuned for best possible performance with your particular usage. Assuming it was tuned at all, it was designed to have good all-around performance on average, taken across a lot of possible usage patterns, some of which are irrelevant to you.

So, it is possible in principle that by implementing the code yourself, you can apply some tweak that helps you and (if the implementers considered that tweak at all) presumably hinders some other user somewhere else. But that's OK, they don't have to use your code. Maybe you like cuckoo hashing and they like linear probing.

Reasons that the implementers might not have considered the tweak include: they're less smart than you (rare, but it happens); the tweak hadn't been invented when they wrote the code and they aren't following the state of the art for that structure / algorithm; they have better things to do with their time and you don't. In those cases perhaps they'd accept a patch from you once you're finished.

There are also reasons other than performance that you might want a data structure very similar to one that your language supports, but with some particular behavior added or removed. If you can't implement that on top of the existing structure then you might well do it from scratch. Obviously it's a significant cost to do so, up front and in future support, but if it's worth it then you do it.

Improve this answer

Comments

2

It may makes sense when you are using a compiled language (like C, Assembly..). When using an interpreted language you will probably have a performance loss, because the native structure parsers are already compiled, and won't waste time "interpreting" the new structure. You will probably do it only when the native structure or algorithm lacks something you need.

Improve this answer

2 Comments

(1) That's assuming the existing implementation isn't written in the very same language. (2) There is no such thing as a compiled or interpreted language. There are languages with vastly worse performance potential because they require many features that aren't free, and because existing implementations aren't great on the performance front. But there are C interpreters and Python compilers.
You are right, I was thinking something like "creating a PHP structure (in PHP) to replace the native one (written in C/C++, if I'm not wrong)".

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.