[perf] Avoid for each loops on ArrayList [2] about batoojpa HOT 28 OPEN

Done...

On Wed, Oct 17, 2012 at 1:23 AM, Thomas Andraschko <[email protected]

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//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 [email protected]
Mobile +90 (532) 713-5384
GTalk [email protected]
WWW http://batoo.jp http://blog.batoo.org/
LinkedIn http://tr.linkedin.com/in/hasanceylan

from batoojpa.

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.

from batoojpa.

Yes. here's the change

from batoojpa.

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 :)

from batoojpa.

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

from batoojpa.

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

from batoojpa.

Thank you Thomas.

The changes pushed to master.

Please close if you think the changes are sufficient.

from batoojpa.

cool :)

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

from batoojpa.

33.50x -> 35x.

Thumbs up!

from batoojpa.

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?

from batoojpa.

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

from batoojpa.

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

from batoojpa.

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

On Thu, Oct 18, 2012 at 12:35 PM, Thomas Andraschko <
[email protected]> 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//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 [email protected]
Mobile +90 (532) 713-5384
GTalk [email protected]
WWW http://batoo.jp http://blog.batoo.org/
LinkedIn http://tr.linkedin.com/in/hasanceylan

from batoojpa.

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.

from batoojpa.

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 [email protected]:

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//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 [email protected]
Mobile +90 (532) 713-5384
GTalk [email protected]
WWW http://batoo.jp http://blog.batoo.org/
LinkedIn http://tr.linkedin.com/in/hasanceylan

from batoojpa.

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

from batoojpa.

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 [email protected]:

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//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 [email protected]
Mobile +90 (532) 713-5384
GTalk [email protected]
WWW http://batoo.jp http://blog.batoo.org/
LinkedIn http://tr.linkedin.com/in/hasanceylan

from batoojpa.

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

from batoojpa.

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.

from batoojpa.

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

from batoojpa.

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

Thanks for the pointers.

from batoojpa.

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?

from batoojpa.

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

from batoojpa.

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.

from batoojpa.

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?

from batoojpa.

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).

from batoojpa.

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.

from batoojpa.

Thank you Jörn,

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

We will make modifications based on that.

from batoojpa.