The most suitable language for computational and expensive memory algorithms

Question

Suppose you need to implement a tool to effectively solve an NP-hard problem, with the inevitable possible explosion of memory usage (the output size in some cases is exponential to the size of the input), and you are especially concerned about the actions of this tool during operation. The source code must also be readable and understandable after the known theory is known, and this requirement is as important as the effectiveness of the tool itself.

I personally believe that 3 languages ​​can be suitable for these three requirements: C ++, scala, java. All of them provide the correct abstraction by data types, which allows you to compare different structures or apply the same algorithms (which is also important) to different data types.

C ++ has the advantage that it is statically compiled and optimized, as well as with the inlining function (if the data structures and algorithms are carefully designed) and other optimization methods can achieve performance close to that of pure C, while maintaining pretty good readability. If you also pay a lot of attention to the presentation of data, you can optimize the cache performance, which can gain orders of magnitude in speed when the cache skip speed is low.

Java is compiled instead of JIT, which allows optimization at runtime, and in this category of algorithms, which can have different types of behavior between different runs, which can be a plus. Instead, I fear that this approach may suffer from the garbage collector, however, in the case of this algorithm, it is common for constant memory allocation, and the performance of the java heap is better than C / C ++, and if you implement your own manager memory inside the language, even achieve good efficiency. Instead, this approach is not capable of embedding a method call (which causes a huge performance hit) and does not give you control over cache performance. Among the pros, there is a better and cleaner syntax than C ++.

My problems with scala are more or less similar to Java, as well as the fact that I can’t control how the language is optimized if I don’t have deep knowledge of the compiler and the standard library. But good: I get very clean syntax :)

How do you feel about this issue? Have you had to deal with this? Could you implement an algorithm with such properties and requirements in any of these languages, or would you suggest something else? How would you compare them?

Answer 1

Usually Id says "C ++" in an instant. The secret is that C ++ simply produces less (memory) garbage that needs to be managed.

On the other hand, your observation that

however, in the case of this algorithm, it usually constantly allocates memory

is a hint that Java / Scala might be more appropriate. But then you can also use a bunch of small objects in C ++. Boost has one that uses the standard allocator interface if memory is used.

Another advantage of C ++, obviously, is the use of abstraction without penalty through templates - i.e. you can easily create common algorithmic components that can interact without imposing runtime overhead due to abstraction. In fact, you noted that

you can achieve performance close to that of pure C, while maintaining pretty good readability.

- it looks wrong: Templates allow C ++ to achieve performance superior to C performance while maintaining a high abstraction.

Answer 2

D can be worth a look, seeing how it tries to become the best C ++.

• With a cursory glance, it has better readability of the source code than C ++, so one of your points is covered.

• It also has memory management , which simplifies the game with algorithms.

• And patterns

• fooobar.com/questions/49313 / ... comparing C ++ and D performance

Answer 3

The language you noticed was my first guess.

Each language has a different approach to solving specific problems, such as compilation, memory management and source code, but theoretically, any of them should correspond to your problem.

It is impossible to determine which is better, and there is probably no significant difference if you are familiar with all of them enough to get around their respective quirks.

And, obviously, if you actually find the need for optimization (I'm not sure if this is given), it is possible in every language. Lower-level languages ​​obviously offer more features, but are also (much) more complex to actually improve.

A separate note on C ++ vs Java: this is truly a holy war, and if you followed the recent development, you will probably have your own opinion. For example, I believe that Java offers good enough aspects to compensate for its shortcomings, as a rule.

One final note about C ++ vs C: To my knowledge, the difference is usually a low enough percentage to ignore this. It makes no difference to the source code, it’s good to go with C, if C ++ can make the source code easier to read, switch to C ++. In any case, the choice is negligible.

In the end, remember that the money spent on several hours of programming / optimization could go into a bit of excellent hardware to make up for the missing tiny details.

It all comes down to: any of your options is good as long as you do it right (domain knowledge).

Answer 4

I would use a language that worked very easily on the algorithm. Get the algorithm right, and it can very easily outweigh any advantage of tweaking the wrong algorithm. Do not be afraid to play in a language that is usually considered slow in speed if this language simplifies the expression of algorithmic ideas. As a rule, it is much easier to rewrite the correct algorithm into a different language than to eek-out the last rejection of speed from the wrong algorithm in the fastest executable language.

So do it in a language that suits you and that is expressive. You can surprise yourself and find that what is being produced is fast enough!