hxcpp Map performance

[Andreas Mokros]

Hi.

I just wrote a small logfile reader. It reads the lines of a
server logfile and counts the requests for certain files by adding
them to a Map applying some filters and so on. It works pretty good in
neko and I thought: why not compile it to cpp, might be a bit faster
then. But in my tests it's like ten times slower than neko. While file
IO (reading the lines) is pretty quick, the handling of a larger Map
(like 3000 keys) seems to be very slow on hxcpp compared to neko (the
same seems to apply to Array and List BTW). I didn't expect to get full
cpp speed due to all this Dynamic constructs in hxcpp but 10(!) times
slower than neko(!) is actually a bit disappointing, isn't it?
Could this be optimized, maybe by using native cpp data structures?

--
Mockey

[Hugh]

Hi

What are your key/value types?  Are you using anonymous value types eg, { file:String, line:Int } or a class/int or something else?

Hugh

[Andreas Mokros]

Hi Hugh.

On Wed, 7 May 2014 05:34:25 -0700 (PDT)
Hugh <game...@gmail.com> wrote:
> What are your key/value types? Are you using anonymous value types
> eg, { file:String, line:Int } or a class/int or something else?

I have 3 Maps in the app:
The first two are simply: Map<String,Int>.
The third one is Map<String,{some anonymous type/typedef}>. I suspected
this could cause the slowdown so I replaced it by
Map<String,SomeEquivalentClass>, which brought a (very) little speed up.
Then I dropped the third Map and saw that the slowdown is already
caused by the Map<String,Int>.
To be precise it seems to become slow when it exceeds a certain size,
like 300 keys or so. I remember I noticed a similar behavior for List in
hxcpp once. I can try to figure out how big that size is exactly if it
helps...

--
Mockey

[Simon Krajewski]

Could you try using StringMap<Int> instead and tell me if that makes a
difference? That way we can make sure that there's no typing
particularity with the abstract Map.

Simon

[Andreas Mokros]

Hi.

On Wed, 07 May 2014 14:54:43 +0200
Simon Krajewski <si...@haxe.org> wrote:
> Could you try using StringMap<Int> instead and tell me if that makes
> a difference? That way we can make sure that there's no typing
> particularity with the abstract Map.

That didn't change anything.
But why is array access only allowed for Map and not for
haxe.ds.StringMap? Isn't this kind of weird?
Anyway, it seems the size of the Map really matters here (for hxcpp).
I'll try to work out some generic test code for that.

--
Mockey

[Simon Krajewski]

Am 07.05.2014 15:54, schrieb Andreas Mokros:
> Hi.
>
> On Wed, 07 May 2014 14:54:43 +0200
> Simon Krajewski <si...@haxe.org> wrote:
>> Could you try using StringMap<Int> instead and tell me if that makes
>> a difference? That way we can make sure that there's no typing
>> particularity with the abstract Map.
> That didn't change anything.
> But why is array access only allowed for Map and not for
> haxe.ds.StringMap? Isn't this kind of weird?

That's because custom array access is a feature of abstract types. Map
is an abstract, but StringMap is a normal class.

Simon

[Andreas Mokros]

Hi.

On Wed, 07 May 2014 16:02:34 +0200
Simon Krajewski <si...@haxe.org> wrote:
> That's because custom array access is a feature of abstract types.
> Map is an abstract, but StringMap is a normal class.

Hm, OK. But it's kind of irritating when you switch from Map to
StringMap. Array access could not be added to StringMap?

--
Mockey

[Joshua Granick]

I think the idea is to use Map in general, and not use the underlying *Map types.

An abstract is compile-time, which allows for additional features, such as array access. In traditional classes, it must be done at runtime, which will not work properly with all target languages, for example, JavaScript

[Andreas Mokros]

Hi.

On Wed, 7 May 2014 14:52:13 +0200
Andreas Mokros <m...@medienpensionat.com> wrote:
> To be precise it seems to become slow when it exceeds a certain size,
> like 300 keys or so. I remember I noticed a similar behavior for List
> in hxcpp once. I can try to figure out how big that size is exactly
> if it helps...

OK, I ran some quick tests for this now. The map has to be much larger
than in my actual app to show some effect. Don't know why, maybe the
effect adds up when other stuff runs in between or when there are
several maps?

Anyway, the effect shows. Comparing hxcpp with neko, hxcpp seems to
perform better until there are around 50000 keys in the map. With
10000 keys or so hxcpp is much faster. With 50000 keys it takes about
the same time as neko. Above 50000 keys hxcpp rapidly performs worse.
With 100000 keys it takes around 50% longer, with 120000 keys it takes
twice as long as neko, with 180000 keys three times as long, with
220000 keys four times as long and so on.
Is this an issue or a consequence of the hxcpp implementation?

Tested on 64bit Linux BTW.

--
Mockey

[Hugh]

I actually got the implementation from the internet and have not tried high-stress tests on it.

One possibility for string keys is that neko might hash the strings, and then do integer compares.  This would have the performance profile you describe - slower with fewer items, and then faster with more.

Looks like it is worth running a profiler over it to see if there is anything that can be done easily to speed it up.

Hugh

[Andreas Mokros]

Hi.

On Wed, 7 May 2014 21:21:22 -0700 (PDT)
Hugh <game...@gmail.com> wrote:
> One possibility for string keys is that neko might hash the strings,
> and then do integer compares. This would have the performance
> profile you describe - slower with fewer items, and then faster with
> more.

Sounds reasonable.

> Looks like it is worth running a profiler over it to see if there is
> anything that can be done easily to speed it up.

std::map cannot be used here?

--
Mockey

[Hugh]

The problem with std::map is that it allocates memory for the nodes, which would need to be freed in some kind of finalizer.  However, there is an overhead with finalizes, so I was not keen on this approach.  It might be possible to make it work with a custom allocator though that uses the GC alloc.

The code is well-defined and relatively small, so it should be easy to try alternate implementations. Possibly even switching implementations once the map hits a certain size (eg, for small object, a linear map, then move to current implementation until 10000 or whatever, then hash the string values).  I'm happy to look at any evidence in this area.

[Cauê Waneck]

If you want, you can try Java (and C#'s) Haxe-only implementations. They are *very* fast - faster than any other native Java/C# implementations I've tested with - and they are quite easy to implement: Just change all NativeArray to whatever you want to use (maybe cpp.NativeArray ?), and implement the following functions:

https://github.com/HaxeFoundation/haxe/blob/development/std/java/_std/haxe/ds/StringMap.hx#L449
arrayCopy and hash.

--
To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en
---
You received this message because you are subscribed to the Google Groups "Haxe" group.
For more options, visit https://groups.google.com/d/optout.