[perf] Avoid for each loops on ArrayList [2] #45

Open
tandraschko opened this Issue Oct 16, 2012 · 28 comments

Comments

Projects
None yet
4 participants

I will provide a patch tomorrow.

If you have a idea how to optimize

  • ManagedList line 192

and replace the iterator loop with a index based loop in

  • PluralAssociationMapping line 573

we only have aroud 15k iterator instances anymore.

900k vs 15k should be a great performance boost.

Owner

hceylan commented Oct 17, 2012

Done...

On Wed, Oct 17, 2012 at 1:23 AM, Thomas Andraschko <notifications@github.com

wrote:

I will provide a patch tomorrow.

If you have a idea how to optimize

  • ManagedList line 192

and replace the iterator loop with a index based loop in

  • PluralAssociationMapping line 573

we only have aroud 15k iterator instances anymore.

900k vs 15k should be a great performance boost.


Reply to this email directly or view it on GitHubhttps://github.com/BatooOrg/BatooJPA/issues/45.

Hasan CEYLAN
Batoo Software & Consultancy
*
*
Have you checked out Batoo JPA - http://batoo.jp http://batoo.jp
Batoo JPA is ~15x faster then the leading JPA implementation!
*
*
http://blog.batoo.org/p/about.html
EMail hceylan@batoo.org
Mobile +90 (532) 713-5384
GTalk hceylan@batoo.org
WWW http://batoo.jp http://blog.batoo.org/
LinkedIn http://tr.linkedin.com/in/hasanceylan

hceylan closed this Oct 17, 2012

Did you also try to optimize PluralAssociationMapping?

Please also re-open it, as i already changed some other parts too. For this i will provide the patch today or tomorrow.

Owner

hceylan commented Oct 17, 2012

Yes. here's the change

hceylan reopened this Oct 17, 2012

The loop at line 573 in PluralAssociationMapping is called very often:

for (final Iterator<E> i = children.iterator(); i.hasNext();) {

I can't see how your changes can optimize this loop, sorry :)

so, iterator instances finally reduced from 5mio to 5204! :)

Sorry but i must add my changes via patch: http://pastebin.com/vjCj4u5L
Somehow rebase and merging does not work fine with eclipse.

Owner

hceylan commented Oct 18, 2012

Thank you Thomas.

The changes pushed to master.

Please close if you think the changes are sufficient.

cool :)

Could you please run the benchmark and post the improvements? thanks!

Owner

hceylan commented Oct 18, 2012

33.50x -> 35x.

Thumbs up!

hceylan closed this Oct 18, 2012

lefou commented Oct 18, 2012

Shouldn't be the instanceof check check against ArrayList instead of List, to ensure, index based loops are actually faster that for each loops, e.g. in CacheInstance, line 275?

Owner

hceylan commented Oct 18, 2012

List could be any List implementation at this stage - user supplied List in the domain, ManagedList or ArrayList.

As far as i now, LinkedList also creates a iterator. So the List check is ok IMO.

Owner

hceylan commented Oct 18, 2012

Iterator is part of Collections API. So any List implementation is fine...

On Thu, Oct 18, 2012 at 12:35 PM, Thomas Andraschko <
notifications@github.com> wrote:

As far as i now, LinkedList also creates a iterator. So the List check is
ok IMO.


Reply to this email directly or view it on GitHubhttps://github.com/BatooOrg/BatooJPA/issues/45#issuecomment-9558531.

Hasan CEYLAN
Batoo Software & Consultancy
*
*
Have you checked out Batoo JPA - http://batoo.jp http://batoo.jp
Batoo JPA is ~15x faster then the leading JPA implementation!
*
*
http://blog.batoo.org/p/about.html
EMail hceylan@batoo.org
Mobile +90 (532) 713-5384
GTalk hceylan@batoo.org
WWW http://batoo.jp http://blog.batoo.org/
LinkedIn http://tr.linkedin.com/in/hasanceylan

lefou commented Oct 18, 2012

Yes, is understand. My concern was about speed improvements. If I understand correctly, you replace an iterator based loop (which a for each loop over any Iterable actually is) by and index based loop. I am not so sure that an index based loop over a LinkedList is actually faster that the Iterator based one. But I didn't tested it, so I cannot claim the opposite, too. Therfore my question.

Owner

hceylan commented Oct 18, 2012

Iterator hits the list 2 times at each iteration .hasNext() and next()
while index based iterator once and +1 to get the size().

So definitely should be better in my opinion...

On Thu, Oct 18, 2012 at 12:42 PM, Tobias Roeser notifications@github.comwrote:

Yes, is understand. My concern was about speed improvements. If I
understand correctly, you replace an iterator based loop (which a for each
loop over any Iterable actually is) by and index based loop. I am not so
sure that an index based loop over a LinkedList is actually faster that the
Iterator based one. But I didn't tested it, so I cannot claim the opposite,
too. Therfore my question.


Reply to this email directly or view it on GitHubhttps://github.com/BatooOrg/BatooJPA/issues/45#issuecomment-9558675.

Hasan CEYLAN
Batoo Software & Consultancy
*
*
Have you checked out Batoo JPA - http://batoo.jp http://batoo.jp
Batoo JPA is ~15x faster then the leading JPA implementation!
*
*
http://blog.batoo.org/p/about.html
EMail hceylan@batoo.org
Mobile +90 (532) 713-5384
GTalk hceylan@batoo.org
WWW http://batoo.jp http://blog.batoo.org/
LinkedIn http://tr.linkedin.com/in/hasanceylan

lefou commented Oct 18, 2012

Hmm, I believe accessing a linked list through an (single) iterator should be much more performant that by index. Let me code a test...

Owner

hceylan commented Oct 18, 2012

LinkedList via iterator must be faster. I agree. But we cannot add to check
instanceof LinkedList for each List throughout.
On the otherhand, as soon as the object becomes managed, the list is
replaced with a ManagedList.

On Thu, Oct 18, 2012 at 12:58 PM, Tobias Roeser notifications@github.comwrote:

Hmm, I believe accessing a linked list through an (single) iterator should
be much more performant that by index. Let me code a test...


Reply to this email directly or view it on GitHubhttps://github.com/BatooOrg/BatooJPA/issues/45#issuecomment-9559138.

Hasan CEYLAN
Batoo Software & Consultancy
*
*
Have you checked out Batoo JPA - http://batoo.jp http://batoo.jp
Batoo JPA is ~15x faster then the leading JPA implementation!
*
*
http://blog.batoo.org/p/about.html
EMail hceylan@batoo.org
Mobile +90 (532) 713-5384
GTalk hceylan@batoo.org
WWW http://batoo.jp http://blog.batoo.org/
LinkedIn http://tr.linkedin.com/in/hasanceylan

lefou commented Oct 18, 2012

You might want to run this snipped, to prove it for yourself.

public static void main(final String[] args) {

        System.out.println("START");
        final LinkedList<Object> linkedList = new LinkedList<Object>();
        for (int i = 1; i < 100000; ++i) {
            linkedList.add(new Object());
        }

        System.out.println("CREATED LIST");

        long millisIterator = 0;
        long millisIndex = 0;

        for (int i = 0; i < 10; ++i) {

            long time = System.currentTimeMillis();
            for (final Object object : linkedList) {
                object.toString();
            }
   if (i > 0)
             millisIterator += System.currentTimeMillis() - time;

            time = System.currentTimeMillis();
            final int size = linkedList.size();
            for (int j = 0; j < size; ++j) {
                final Object object = linkedList.get(j);
                object.toString();
            }
            if (i > 0)
    millisIndex += System.currentTimeMillis() - time;

            System.out.println("Iterator-based milliseconds:" + millisIterator);
            System.out.println("Index-based milliseconds:" + millisIndex);
        }

        System.out.println("FINISHED");
        System.out.println("Iterator-based milliseconds:" + millisIterator);
        System.out.println("Index-based milliseconds:" + millisIndex);

    }

Although, my laptops changes cpu speed when getting hot, here are my results:

START
CREATED LIST
Iterator-based milliseconds:108
Index-based milliseconds:9925
Iterator-based milliseconds:126
Index-based milliseconds:21325
Iterator-based milliseconds:162
Index-based milliseconds:31018
Iterator-based milliseconds:179
Index-based milliseconds:40691
Iterator-based milliseconds:211
Index-based milliseconds:48136
Iterator-based milliseconds:225
Index-based milliseconds:56543
Iterator-based milliseconds:241
Index-based milliseconds:67650
Iterator-based milliseconds:256
Index-based milliseconds:78748
Iterator-based milliseconds:278
Index-based milliseconds:89868
FINISHED
Iterator-based milliseconds:278
Index-based milliseconds:89868

lefou commented Oct 18, 2012

My initial point was a case like this one:

@@ -272,8 +273,16 @@
                }

                // populate the reference list and put to cache
-               for (final Object child : collection.getDelegate()) {
-                       references.add(new CacheReference(metamodel, child));
+               if (collection.getDelegate() instanceof List) {
+                   final List<?> delegateList = (List<?>) collection.getDelegate();
+                   for (int i = 0; i < delegateList.size(); i++) {
+                       references.add(new CacheReference(metamodel, delegateList.get(i)));
+                   }
+               }
+               else {
+               for (final Object child : collection.getDelegate()) {
+                       references.add(new CacheReference(metamodel, child));
+               }
                }

                this.pluralMappings.put(mapping.getPath(), references);

The newly introduced instanceof should be more specific and only check for implementations, that are actually faster when traversed by index, like an ArrayList might be.

lefou commented Oct 18, 2012

But even than. If I replace LinkedList by ArrayList in the example above, I got:
Iterator-based milliseconds:165
Index-based milliseconds:227

Owner

hceylan commented Oct 18, 2012

Ok. This is becoming rather interesting.
I'll reopen to issue and revisit it very soon.

Thanks for the pointers.

hceylan reopened this Oct 18, 2012

Owner

hceylan commented Oct 24, 2012

Way to go would be to modify the Benchmark and

  • add merge() test.
  • replace original ArrayList collection with `LinkedList,
  • put a break point in ,LinkedList.get()and hunt down the index based operations that are not yet replaced with internalManagedList`

This will indicate not not only LinkedList any user supplied List is handled with standard for - each loop.

Thomas & Lefou , do you think these bullet points makes sense?

Sorry but didn't get it. Would you like to replace all ArrayLists with LinkedLists?

Owner

hceylan commented Oct 24, 2012

No not at all.

Now that we replaced all for - each loops with index based loops, Lefou earlier pointed out that somehow if we encounter a List with underlying LinkedList, we will treat this List instance with index based iterations.

However LinkedList is specifically designed to be faster with for each (iteration) iterators. LinkedList is absolutely terrible with index based iterations. This is by design and due to iterating up to the index for each get()

Example
1 iteration to get the 1st item
2 iterations to get the 2nd item
...
n iterations to get the nth item.

Total n * n + 1 / 2 iterations - taking way too long then the optimization gain.

Only effected Batoo JPA iterations should be reverted to for each iterations...

Hope that clarifies it.

IMO it would be ok if we just replace the "instanceof List" with "instanceof ArrayList" but your propsal is of course better for users with LinkedLists.
I always use List as interface in my mapping, so in this case Batoo is always using ArrayList, right?

lefou commented Oct 24, 2012

I also prefer to replace the "instanceof List" with "instanceof ArrayList", add do index-based iteration only if the list is an ArrayList. Of course, if you know for sure that your ManagedList's are faster with indexed loops but they don't inherit ArrayList, you could enhance the check to: (list instanceof ArrayList || list instanceof ManagedList).

I think a check for instanceof java.util.RandomAccess would be right think to do, as that interface is intended for this use case:

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

Owner

hceylan commented Oct 25, 2012

Thank you Jörn,

I must admit never knew it. Definitely that serves that purpose...

We will make modifications based on that.

@rnapoles rnapoles pushed a commit to rnapoles/Android-BatooJPA that referenced this issue Nov 1, 2016

hceylan Further performance changes e9f765e

@rnapoles rnapoles pushed a commit to rnapoles/Android-BatooJPA that referenced this issue Nov 1, 2016

hceylan Performance Improvements ed5c073
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment