Optimizing Ada

Optimizing Ada

[kennethesills]

tl;dr Just started using Ada. Two code samples are on the bottom, one is Ada, one is Rust. The functions simply return a map of words and how often they are used in a given string. The Ada one is far slower even though almost all other test cases are faster, and I wanted to know how I might be able to optimize it a bit.

And for those who want a bit more detail:

I decided to give Ada a spin recently and started working on Martyr's Mega Project List to learn the language. I use this to judge the languages performance, readability, etc. And have implemented in quite a few languages.

I've also recently been experimenting with Rust, which (if you don't already know) is another safety-oriented language, but far newer and some bit more C++-ish. So simultaneously, I've been working on the Rust version.

So far, Ada has been more verbose (by far), but the tooling (compiler and GPS), but also comes out easier for me to read looking back at the code. The only real snags I've hit with Ada is trouble with finding documentation on the standard library.

The performance Ada has been putting out is actually very impressive, as well. Consistently demolishing Rust's performance, and sometimes even C++:

Count_Vowels:
Rust => 19 ns
Ada  => .5 ns (-O2 actually optimizes the benchmark away entirely).

Reverse String:
Rust => 111 ns
Ada  => 29.3 ns

Is Palindrome:
Rust => 119 ns (Rust version is actually case sensitive, so technically "broken".)
Ada  => 56.1 ns

To Pig Latin (Best/Worst/Middle):
Rust => 91 - 141 - 140 ns
Ada  => 34 - 44  - 35 ns


I just finished implementing the Count Word Use function (pretty self-explanatory - makes a map of how often words are used) for both languages, and expected the same result in terms of performance. However, the actuals were completely opposite to my expectations:

Count Word Use:
Rust => 2763 ns (Again, case sensitive, so technically it's "broken".)
Ada  => 7436.9 ns

So I was just wondering if anyone could help me optimize my Ada code a bit, as well as tell me how I'm doing in terms of general code style and idiomatic code writing.

Here are the two code samples:

Ada Code : http://pastebin.com/vDbdXCYD (a quotation mark messed up highlighting near bottom)
Rust Code: http://pastebin.com/1ZVL7Pjf

Thank you and have a great day.

Re: Optimizing Ada

[Jeffrey Carter]

On 10/01/2013 07:58 PM, kennethesills@gmail.com wrote:
>
> Count Word Use:
> Rust => 2763 ns (Again, case sensitive, so technically it's "broken".)
> Ada  => 7436.9 ns

In other words, Ada is the fastest correct implementation you have. I can write 
a version in Ada that's much faster than your Rust version if it doesn't have to 
be correct :)

-- 
Jeff Carter
"This school was here before you came,
and it'll be here before you go."
Horse Feathers
48

Re: Optimizing Ada

[kennethesills]

> Ada is the fastest correct implementation you have.

Yes. However, is case sensitivity the reason for a 2.7x slow down? Highly unlikely. In fact, using case-sensitive comparisons in Ada only reduce the time taken by around 50ns. So I just disregarded that fact.

Re: Optimizing Ada

[Jeffrey Carter]

On 10/01/2013 08:53 PM, kennethesills@gmail.com wrote:
>> Ada is the fastest correct implementation you have.
>
> Yes. However, is case sensitivity the reason for a 2.7x slow down? Highly
> unlikely. In fact, using case-sensitive comparisons in Ada only reduce the
> time taken by around 50ns. So I just disregarded that fact.

I agree that the implementation of Indefinite_Hashed_Maps is probably the 
culprit, but until you have an apples-to-apples comparison, you have no 
complaint. (Actually, I can't think of any application that could use such a 
function where the difference would prevent it from meeting reasonable timing 
requirements, so you probably have no complaint anyway.)

-- 
Jeff Carter
"This school was here before you came,
and it'll be here before you go."
Horse Feathers
48

Re: Optimizing Ada

[kennethesills]

Fair enough.

Other than that, is the code itself clean/idiomatic enough? Not teaching myself any bad habits?

Re: Optimizing Ada

[Egil H H]

On Wednesday, October 2, 2013 4:58:40 AM UTC+2, kennet...@gmail.com wrote:
> 
<snip>
>  The only real snags I've hit with Ada is trouble with finding documentation on the standard library.
> 

The Standard Library is defined in Annex A of the reference manual,
http://www.adaic.org/resources/add_content/standards/12rm/html/RM-A.html

Specifically, see section A.18.4 for a description of Maps:
http://www.adaic.org/resources/add_content/standards/12rm/html/RM-A-18-4.html

> 
> Ada Code : http://pastebin.com/vDbdXCYD (a quotation mark messed up highlighting near bottom)
> 


You could try to preallocate space in the Word_Map by calling
Word_Map.Reserve_Capacity(some_fairly_large_number);

Also, you're calling Update_Element even for new words. Depending on your dataset, that could potentially be a lot of unneccessary callbacks. Try this:

Word_Map.Insert(Key      => Word,
                New_Item => 1,      -- <----
                Position => Location,
                Inserted => Added);
if not Added then
   Word_Map.Update_Element(Position => Location,
                           Process   => Increment_By_One'Access);
end if;



Rust probably have a faster hash function (seems they use SipHash 2-4). Try to implement the same algorithm in Ada, see if that makes a difference.

Re: Optimizing Ada

[Simon Wright]

kennethesills@gmail.com writes:

> So I was just wondering if anyone could help me optimize my Ada code a
> bit, as well as tell me how I'm doing in terms of general code style
> and idiomatic code writing.

Looks pretty good to me (we disagree about having a space between the
subprogram name and the opening paren, but then the ALRM is wrong about
that too :-)

I'm not sure that pragma Inline is meant to work when applied to a
subprogram body, so I'd apply it to the spec (I always write specs,
because I've set the GNAT style options to standard (-gnaty), and that
warns me about missing specs - and about missing spaces, see above).

GNAT may not have implemented your Inline anyway. There's a GNAT pragma
Inline_Always, and there are switches (-gnatn, -gnatN I think) that
affect inlining. The last time I did a check, inlining made my program
slower - cache effects, presumably. That was on powerpc.

AdaCore's house rules don't allow I as a variable name (confusion
potential), they start at J.

I wonder whether your performance problem is caused by using a function?
The internal Word_Map is, I think, going to be copied to the destination
and then finalized. Could you use an out parameter? (remembering to
clear it before adding ne new content).

Re: Optimizing Ada

[Jacob Sparre Andersen]

kennethesills@gmail.com writes:

> Other than that, is the code itself clean/idiomatic enough? Not
> teaching myself any bad habits?

There are some style issues:

- space before parenthesis (i.e. "procedure Increment_By_One (...").
- lower-case keywords (i.e. "array", "others", ...).

You may get a performance gain by using an extended return statement:

   return Word_Map : Word_Count_Maps.Map do
      ...
   end return;

Greetings,

Jacob
-- 
"Science is like sex: sometimes something useful comes out,
 but that is not the reason we are doing it"
                                          -- Richard Feynman

Re: Optimizing Ada

[Marius Amado-Alves]

The Ada code is perfect (only the body looks indented only 2 spaces instead of 3, first level).

How do the performances *scale*? Have you tried say 1, 10... 1_000_000 words?

Related: separate load time, loop time.

Re: Optimizing Ada

[Marius Amado-Alves]

> - space before parenthesis (i.e. "procedure Increment_By_One (...").
> - lower-case keywords (i.e. "array", "others", ...).

Perfect except that, yes; and correct spelling is "occurrence".

Re: Optimizing Ada

[kennethesills]

> You may get a performance gain by using an extended return statement:

That was exactly what I needed, apparently; Cut the run-time in half.

Re: Optimizing Ada

[kennethesills]

> The Ada code is perfect (only the body looks indented only 2 spaces instead of 3, first level).
Ah, an unfortunate copy/paste issue.

> How do the performances *scale*? Have you tried say 1, 10... 1_000_000 words?
Yes, sir. It's pretty consistent (stays within an ~300ns range) when I tested ranging from 10_000 to 1_000_000 iterations.

Re: Optimizing Ada

[kennethesills]

> I wonder whether your performance problem is caused by using a function?
> The internal Word_Map is, I think, going to be copied to the destination
> and then finalized. Could you use an out parameter? (remembering to 
> clear it before adding ne new content).

That was exactly it, actually. As per Jacob's suggestion - I used an extended return and it dropped down to 2900ns.

Another suggestion was that Rust uses a faster hash function (SipHash 2-4). 

Re: Optimizing Ada

[Jeffrey Carter]

On 10/01/2013 09:24 PM, kennethesills@gmail.com wrote:
>
> Other than that, is the code itself clean/idiomatic enough? Not teaching myself any bad habits?

The code reads fine. There are some stylistic differences from how I'd write it, 
but that's true for everyone. I haven't seen that version of Insert used very 
much, so I might add a comment to remind the reader how it works when the key is 
already in the map. I would probably avoid calling Update_Element when Insert 
succeeds. Perhaps most important, I would be leery of writing a function that 
returns a map, but that may be a requirement out of your control

-- 
Jeff Carter
"Go and boil your bottoms."
Monty Python & the Holy Grail
01

Re: Optimizing Ada

[John B. Matthews]

In article <l2g6i7$8mm$1@dont-email.me>,
 Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> wrote:

> On 10/01/2013 08:53 PM, kennethesills@gmail.com wrote:
> >> Ada is the fastest correct implementation you have.
> >
> > Yes. However, is case sensitivity the reason for a 2.7x slow down? 
> > Highly unlikely. In fact, using case-sensitive comparisons in Ada 
> > only reduce the time taken by around 50ns. So I just disregarded 
> > that fact.
> 
> I agree that the implementation of Indefinite_Hashed_Maps is probably 
> the culprit, but until you have an apples-to-apples comparison, you 
> have no complaint. (Actually, I can't think of any application that 
> could use such a function where the difference would prevent it from 
> meeting reasonable timing requirements, so you probably have no 
> complaint anyway.)

kennethesills: For comparison with Indefinite_Hashed_Maps, this example 
uses an instance of Ada.Strings.Bounded.Generic_Bounded_Length as the 
Key_Type in an instance of Ada.Containers.Hashed_Maps. Your problem 
domain may suggest a suitable maximum length.

<http://home.roadrunner.com/~jbmatthews/jumble.html>

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>