[jira] [Created] (IGNITE-4661) Optimizations: optimize PagesList.removeDataPage

[Anton Vinogradov (Jira)]

Semen Boikov created IGNITE-4661:
------------------------------------

             Summary: Optimizations: optimize PagesList.removeDataPage
                 Key: IGNITE-4661
                 URL: https://issues.apache.org/jira/browse/IGNITE-4661
             Project: Ignite
          Issue Type: Task
          Components: cache
            Reporter: Semen Boikov
             Fix For: 2.0


Optimization for new PageMemory approach (IGNITE-3477, branch ignite-3477).
Currently PagesList.removeDataPage requires linear search by page ID, need check if it makes sense to change structure of PagesList's element from list to hash table.
Here are links to proposed hash table alrorithm:
http://codecapsule.com/2013/11/11/robin-hood-hashing
http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/

Note: with hash table approach 'take' from PagesList will require linear search, so we'll also need some heuristic to make it more optimal.

For more details see:
IgniteCacheOffheapManagerImpl.update -> FreeListImpl.insertDataRow,
IgniteCacheOffheapManagerImpl.update -> FreeListImpl.removeDataRowByLink.

To check result of optimization IgnitePutRandomValueSizeBenchmark can be used.



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)