Bad performance pruning large caches

[javafanboy]

I have previously reported (#95) problems with very poor performance pruning large caches due to a code line where the first element in an array list is removed in every iteration of the list resulting in a O(n ** 2) algorithm. I got the response the coherence CE team would look into the problem.

This problem is present in the class OldCache method pruneIncremental at the line "iterEvict.remove(); // COH-23644".

A better solution, in my mind, would be to just ignore removing the element as the whole structure is anyway released as garbage once the iteration ios completed. As an alternative one could iterate the list from the end as deleting the last element of an array list seem to be an optimized case (at least in later SDKs).

Due to the very slow performance of the algorithm as it is written now I doubt memory will actually be released faster with the current implementation (according to discussion on my previous report this seemed to be the motivation of introducing this line / COH-23644) compared to much faster getting through the whole structure and releasing it at the end...

I have not tested the new v14.1.1.0.13 release or verified if the iterated structure somewhere else in the code has been changed to no longer be an ArrayList (a LinkedList, is generally slower but would in this specific algorithm be better as removal of any elements is a O(1) operation) but a quick check of the source show this line to still be present and the problem probably not fixed :-(

To work around this problem we have ourselves removed the offending line and rebuilt Coherence CE for our use but would like to not having to perform this step for every release...

[fryp]

This issue is fixed in the upcoming Coherence CE releases: 23.03.1 - commits 75b8f39 and 914d593, 22.06.5 - commits 3f3974d and b8dcbcc, and 14.1.1.0.14 - commits 65e8553 and e7c02bb

[javafanboy]

Thanks - will test it with an upcoming release of our software!

…

On Fri, Jul 14, 2023, 21:11 Patrick Fry ***@***.***> wrote: This issue is fixed in the upcoming Coherence CE releases: 23.03.1 - commit 914d593 <914d593>, 22.06.5 - commit b8dcbcc <b8dcbcc>, and 14.1.1.0.14 - commit e7c02bb <e7c02bb> — Reply to this email directly, view it on GitHub <#103 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADXQF3XAPYAZC3TUVYR6ADXQGKXZANCNFSM6AAAAAAXDRXGH4> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[fryp]

The fix was to replace the iterEvict.remove() with an iterEvict.set(null) which does not resize the ArrayList. The change does provide the original intention for adding the iterEvict.remove(), which was to release the reference to the cache entry so that it is a candidate for garbage collection.

[javafanboy]

That sounds like a great fix.

…

On Thu, Jul 20, 2023, 16:38 Patrick Fry ***@***.***> wrote: The fix was to replace the iterEvict.remove() with an iterEvict.set(null) which does not resize the ArrayList. The change does provide the original intention for adding the iterEvict.remove(), which was to release the reference to the cache entry so that it is a candidate for garbage collection. — Reply to this email directly, view it on GitHub <#103 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADXQF4VHTI34ZE55GPV3D3XRE7BFANCNFSM6AAAAAAXDRXGH4> . You are receiving this because you authored the thread.Message ID: ***@***.***>