diff --git a/libs/image/tiles3/KisTiledExtentManager.h b/libs/image/tiles3/KisTiledExtentManager.h
--- a/libs/image/tiles3/KisTiledExtentManager.h
+++ b/libs/image/tiles3/KisTiledExtentManager.h
@@ -20,6 +20,7 @@
 #define KISTILEDEXTENTMANAGER_H
 
 #include <QMutex>
+#include <QReadWriteLock>
 #include <QMap>
 #include <QRect>
 #include "kritaimage_export.h"
@@ -27,6 +28,39 @@
 
 class KRITAIMAGE_EXPORT KisTiledExtentManager
 {
+    static const int InitialBufferSize = 8;
+
+    class Data
+    {
+    public:
+        Data();
+        ~Data();
+
+        inline bool add(int index);
+        inline bool remove(int index);
+        void clear();
+        bool isEmpty();
+        int min();
+        int max();
+
+    public:
+        mutable QReadWriteLock m_extentGuard;
+
+    private:
+        void migrate(int index);
+        void updateMin();
+        void updateMax();
+
+    private:
+        int m_min;
+        int m_max;
+        int m_offset;
+        int m_capacity;
+        int m_count;
+        QAtomicInt *m_buffer;
+        QReadWriteLock m_lock;
+    };
+
 public:
     KisTiledExtentManager();
 
@@ -42,10 +76,9 @@
     void updateExtent();
 
 private:
-    mutable QMutex m_mutex;
-    QMap<int, int> m_colMap;
-    QMap<int, int> m_rowMap;
     QRect m_currentExtent;
+    Data m_colsData;
+    Data m_rowsData;
 };
 
 #endif // KISTILEDEXTENTMANAGER_H
diff --git a/libs/image/tiles3/KisTiledExtentManager.cpp b/libs/image/tiles3/KisTiledExtentManager.cpp
--- a/libs/image/tiles3/KisTiledExtentManager.cpp
+++ b/libs/image/tiles3/KisTiledExtentManager.cpp
@@ -24,47 +24,178 @@
 #include "kis_assert.h"
 #include "kis_global.h"
 
-namespace {
+KisTiledExtentManager::Data::Data()
+    : m_min(INT_MAX), m_max(INT_MIN), m_count(0)
+{
+    QWriteLocker l(&m_lock);
+    m_capacity = InitialBufferSize;
+    m_offset = m_capacity >> 1;
+    m_buffer = new QAtomicInt[m_capacity];
+}
+
+KisTiledExtentManager::Data::~Data()
+{
+    QWriteLocker l(&m_lock);
+    delete[] m_buffer;
+}
 
-inline bool addTileToMap(int index, QMap<int, int> *map)
+inline bool KisTiledExtentManager::Data::add(int index)
 {
+    QReadLocker l(&m_lock);
+    int currentIndex = m_offset + index;
+
+    if (currentIndex < 0 || currentIndex >= m_capacity) {
+        l.unlock();
+        migrate(index);
+        l.relock();
+        currentIndex = m_offset + index;
+    }
+
+    KIS_ASSERT_RECOVER_NOOP(m_buffer[currentIndex].loadAcquire() >= 0);
     bool needsUpdateExtent = false;
 
-    auto it = map->find(index);
+    if (!m_buffer[currentIndex].loadAcquire()) {
+        QWriteLocker lock(&m_extentGuard);
+
+        if (!m_buffer[currentIndex].load()) {
+            m_buffer[currentIndex].store(1);
 
-    if (it == map->end()) {
-        map->insert(index, 1);
-        needsUpdateExtent = true;
+            if (m_min > index) m_min = index;
+            if (m_max < index) m_max = index;
+
+            ++m_count;
+            needsUpdateExtent = true;
+        } else {
+            m_buffer[currentIndex].ref();
+        }
     } else {
-        KIS_ASSERT_RECOVER_NOOP(*it > 0);
-        (*it)++;
+        m_buffer[currentIndex].ref();
     }
 
     return needsUpdateExtent;
 }
 
-inline bool removeTileFromMap(int index, QMap<int, int> *map)
+inline bool KisTiledExtentManager::Data::remove(int index)
 {
+    QReadLocker l(&m_lock);
+    int currentIndex = m_offset + index;
+
+    if (currentIndex < 0 || currentIndex >= m_capacity) {
+        l.unlock();
+        migrate(index);
+        l.relock();
+        currentIndex = m_offset + index;
+    }
+
+    KIS_ASSERT_RECOVER_NOOP(m_buffer[currentIndex].loadAcquire() > 0);
     bool needsUpdateExtent = false;
 
-    auto it = map->find(index);
+    if (m_buffer[currentIndex].loadAcquire() == 1) {
+        QWriteLocker lock(&m_extentGuard);
 
-    if (it == map->end()) {
-        KIS_ASSERT_RECOVER_NOOP(0 && "sanity check failed: the tile has already been removed!");
-    } else {
-        KIS_ASSERT_RECOVER_NOOP(*it > 0);
-        (*it)--;
+        if (m_buffer[currentIndex].load() == 1) {
+            m_buffer[currentIndex].store(0);
+
+            if (m_min == index) updateMin();
+            if (m_max == index) updateMax();
 
-        if (*it <= 0) {
-            map->erase(it);
+            --m_count;
             needsUpdateExtent = true;
+        } else {
+            KIS_ASSERT_RECOVER_NOOP(0 && "sanity check failed: the tile has already been removed!");
         }
+    } else {
+        m_buffer[currentIndex].deref();
     }
 
     return needsUpdateExtent;
 }
 
+void KisTiledExtentManager::Data::clear()
+{
+    QWriteLocker l(&m_lock);
+    for (int i = 0; i < m_capacity; ++i) {
+        m_buffer[i].store(0);
+    }
+
+    QWriteLocker lock(&m_extentGuard);
+    m_count = 0;
+}
+
+/*
+ * We don't take locks in isEmpty(), min() and max(),
+ * cause it will be taken in updateExtent()
+ */
+
+bool KisTiledExtentManager::Data::isEmpty()
+{
+    return m_count == 0;
+}
+
+int KisTiledExtentManager::Data::min()
+{
+    return m_min;
+}
+
+int KisTiledExtentManager::Data::max()
+{
+    return m_max;
+}
+
+void KisTiledExtentManager::Data::migrate(int index)
+{
+    QWriteLocker l(&m_lock);
+    int oldCapacity = m_capacity;
+    int oldOffset = m_offset;
+    int currentIndex = m_offset + index;
+
+    while (currentIndex < 0 || currentIndex >= m_capacity) {
+        m_capacity <<= 1;
+        m_offset <<= 1;
+        currentIndex = m_offset + index;
+    }
+
+    if (m_capacity != oldCapacity) {
+        QAtomicInt *newBuffer = new QAtomicInt[m_capacity];
+        int start = m_offset - oldOffset;
+
+        for (int i = 0; i < oldCapacity; ++i) {
+            newBuffer[start + i].store(m_buffer[i].load());
+        }
+
+        delete[] m_buffer;
+        m_buffer = newBuffer;
+    }
+}
+
+/*
+ * We don't take locks in updateMin() and updateMax(),
+ * cause it will be taken in add/remove when incrementing from 0 to 1
+ * or decrementing from 1 to 0
+ */
+
+void KisTiledExtentManager::Data::updateMin()
+{
+    for (int i = 0; i < m_capacity; ++i) {
+        int current = m_buffer[i].load();
 
+        if (current > 0) {
+            m_min = current;
+            break;
+        }
+    }
+}
+
+void KisTiledExtentManager::Data::updateMax()
+{
+    for (int i = m_capacity - 1; i >= 0; ++i) {
+        int current = m_buffer[i].load();
+
+        if (current > 0) {
+            m_max = current;
+            break;
+        }
+    }
 }
 
 KisTiledExtentManager::KisTiledExtentManager()
@@ -73,12 +204,10 @@
 
 void KisTiledExtentManager::notifyTileAdded(int col, int row)
 {
-    QMutexLocker l(&m_mutex);
-
     bool needsUpdateExtent = false;
 
-    needsUpdateExtent |= addTileToMap(col, &m_colMap);
-    needsUpdateExtent |= addTileToMap(row, &m_rowMap);
+    needsUpdateExtent |= m_colsData.add(col);
+    needsUpdateExtent |= m_rowsData.add(row);
 
     if (needsUpdateExtent) {
         updateExtent();
@@ -87,12 +216,10 @@
 
 void KisTiledExtentManager::notifyTileRemoved(int col, int row)
 {
-    QMutexLocker l(&m_mutex);
-
     bool needsUpdateExtent = false;
 
-    needsUpdateExtent |= removeTileFromMap(col, &m_colMap);
-    needsUpdateExtent |= removeTileFromMap(row, &m_rowMap);
+    needsUpdateExtent |= m_colsData.remove(col);
+    needsUpdateExtent |= m_rowsData.remove(row);
 
     if (needsUpdateExtent) {
         updateExtent();
@@ -101,14 +228,12 @@
 
 void KisTiledExtentManager::replaceTileStats(const QVector<QPoint> &indexes)
 {
-    QMutexLocker l(&m_mutex);
-
-    m_colMap.clear();
-    m_rowMap.clear();
+    m_colsData.clear();
+    m_rowsData.clear();
 
     Q_FOREACH (const QPoint &index, indexes) {
-        addTileToMap(index.x(), &m_colMap);
-        addTileToMap(index.y(), &m_rowMap);
+        m_colsData.add(index.x());
+        m_rowsData.add(index.y());
     }
 
     updateExtent();
@@ -116,32 +241,37 @@
 
 void KisTiledExtentManager::clear()
 {
-    QMutexLocker l(&m_mutex);
+    m_colsData.clear();
+    m_rowsData.clear();
 
-    m_colMap.clear();
-    m_rowMap.clear();
+    QWriteLocker cl(&m_colsData.m_extentGuard);
+    QWriteLocker rl(&m_rowsData.m_extentGuard);
     m_currentExtent = QRect(qint32_MAX, qint32_MAX, 0, 0);
-
 }
 
 QRect KisTiledExtentManager::extent() const
 {
-    QMutexLocker l(&m_mutex);
+    QReadLocker cl(&m_colsData.m_extentGuard);
+    QReadLocker rl(&m_rowsData.m_extentGuard);
     return m_currentExtent;
 }
 
 void KisTiledExtentManager::updateExtent()
 {
-    KIS_ASSERT_RECOVER_RETURN(m_colMap.isEmpty() == m_rowMap.isEmpty());
+    QWriteLocker cl(&m_colsData.m_extentGuard);
+    QWriteLocker rl(&m_rowsData.m_extentGuard);
+
+    bool colsEmpty = m_colsData.isEmpty();
+    bool rowsEmpty = m_rowsData.isEmpty();
+    KIS_ASSERT_RECOVER_RETURN(colsEmpty == rowsEmpty);
 
-    // here we check for only one map for efficiency reasons
-    if (m_colMap.isEmpty()) {
+    if (colsEmpty && rowsEmpty) {
         m_currentExtent = QRect(qint32_MAX, qint32_MAX, 0, 0);
     } else {
-        const int minX = m_colMap.firstKey() * KisTileData::WIDTH;
-        const int maxPlusOneX = (m_colMap.lastKey() + 1) * KisTileData::WIDTH;
-        const int minY = m_rowMap.firstKey() * KisTileData::HEIGHT;
-        const int maxPlusOneY = (m_rowMap.lastKey() + 1) * KisTileData::HEIGHT;
+        const int minX = m_colsData.min() * KisTileData::WIDTH;
+        const int maxPlusOneX = (m_colsData.max() + 1) * KisTileData::WIDTH;
+        const int minY = m_rowsData.min() * KisTileData::HEIGHT;
+        const int maxPlusOneY = (m_rowsData.max() + 1) * KisTileData::HEIGHT;
 
         m_currentExtent =
             QRect(minX, minY,
@@ -149,4 +279,3 @@
                   maxPlusOneY - minY);
     }
 }
-
diff --git a/libs/image/tiles3/kis_tile_data.cc b/libs/image/tiles3/kis_tile_data.cc
--- a/libs/image/tiles3/kis_tile_data.cc
+++ b/libs/image/tiles3/kis_tile_data.cc
@@ -35,6 +35,31 @@
 const qint32 KisTileData::WIDTH = __TILE_DATA_WIDTH;
 const qint32 KisTileData::HEIGHT = __TILE_DATA_HEIGHT;
 
+SimpleCache KisTileData::m_cache;
+
+SimpleCache::~SimpleCache()
+{
+    clear();
+}
+
+void SimpleCache::clear()
+{
+    QWriteLocker l(&m_cacheLock);
+    quint8 *ptr = 0;
+
+    while (m_4Pool.pop(ptr)) {
+        BoostPool4BPP::free(ptr);
+    }
+
+    while (m_8Pool.pop(ptr)) {
+        BoostPool8BPP::free(ptr);
+    }
+
+    while (m_16Pool.pop(ptr)) {
+        free(ptr);
+    }
+}
+
 
 KisTileData::KisTileData(qint32 pixelSize, const quint8 *defPixel, KisTileDataStore *store)
     : m_state(NORMAL),
@@ -72,7 +97,7 @@
       m_pixelSize(rhs.m_pixelSize),
       m_store(rhs.m_store)
 {
-    if(checkFreeMemory) {
+    if (checkFreeMemory) {
         m_store->checkFreeMemory();
     }
     m_data = allocateData(m_pixelSize);
@@ -90,7 +115,7 @@
 {
     quint8 *it = m_data;
 
-    for (int i = 0; i < WIDTH*HEIGHT; i++, it += m_pixelSize) {
+    for (int i = 0; i < WIDTH * HEIGHT; i++, it += m_pixelSize) {
         memcpy(it, defPixel, m_pixelSize);
     }
 }
@@ -103,7 +128,7 @@
     }
 
     KisTileData *clone = 0;
-    while(m_clonesStack.pop(clone)) {
+    while (m_clonesStack.pop(clone)) {
         delete clone;
     }
 
@@ -120,15 +145,18 @@
 {
     quint8 *ptr = 0;
 
-    switch(pixelSize) {
-    case 4:
-        ptr = (quint8*)BoostPool4BPP::malloc();
-        break;
-    case 8:
-        ptr = (quint8*)BoostPool8BPP::malloc();
-        break;
-    default:
-        ptr = (quint8*) malloc(pixelSize * WIDTH * HEIGHT);
+    if (!m_cache.pop(pixelSize, ptr)) {
+        switch (pixelSize) {
+        case 4:
+            ptr = (quint8*)BoostPool4BPP::malloc();
+            break;
+        case 8:
+            ptr = (quint8*)BoostPool8BPP::malloc();
+            break;
+        default:
+            ptr = (quint8*) malloc(pixelSize * WIDTH * HEIGHT);
+            break;
+        }
     }
 
     return ptr;
@@ -136,15 +164,18 @@
 
 void KisTileData::freeData(quint8* ptr, const qint32 pixelSize)
 {
-    switch(pixelSize) {
-    case 4:
-        BoostPool4BPP::free(ptr);
-        break;
-    case 8:
-        BoostPool8BPP::free(ptr);
-        break;
-    default:
-        free(ptr);
+    if (!m_cache.push(pixelSize, ptr)) {
+        switch (pixelSize) {
+        case 4:
+            BoostPool4BPP::free(ptr);
+            break;
+        case 8:
+            BoostPool8BPP::free(ptr);
+            break;
+        default:
+            free(ptr);
+            break;
+        }
     }
 }
 
@@ -166,12 +197,12 @@
 
         KisTileDataStoreIterator *iter = KisTileDataStore::instance()->beginIteration();
 
-        while(iter->hasNext()) {
+        while (iter->hasNext()) {
             KisTileData *item = iter->next();
 
             // first release all the clones
             KisTileData *clone = 0;
-            while(item->m_clonesStack.pop(clone)) {
+            while (item->m_clonesStack.pop(clone)) {
                 delete clone;
             }
 
@@ -199,6 +230,7 @@
 
         if (!failedToLock) {
             // purge the pools memory
+            m_cache.clear();
             BoostPool4BPP::purge_memory();
             BoostPool8BPP::purge_memory();
 
diff --git a/libs/image/tiles3/kis_tile_data_interface.h b/libs/image/tiles3/kis_tile_data_interface.h
--- a/libs/image/tiles3/kis_tile_data_interface.h
+++ b/libs/image/tiles3/kis_tile_data_interface.h
@@ -41,6 +41,57 @@
 typedef KisTileDataList::const_iterator KisTileDataListConstIterator;
 
 
+class SimpleCache
+{
+public:
+    SimpleCache() = default;
+    ~SimpleCache();
+
+    bool push(int pixelSize, quint8 *&ptr)
+    {
+        QReadLocker l(&m_cacheLock);
+        switch (pixelSize) {
+        case 4:
+            m_4Pool.push(ptr);
+            break;
+        case 8:
+            m_8Pool.push(ptr);
+            break;
+        case 16:
+            m_16Pool.push(ptr);
+            break;
+        default:
+            return false;
+        }
+
+        return true;
+    }
+
+    bool pop(int pixelSize, quint8 *&ptr)
+    {
+        QReadLocker l(&m_cacheLock);
+        switch (pixelSize) {
+        case 4:
+            return m_4Pool.pop(ptr);
+        case 8:
+            return m_8Pool.pop(ptr);
+        case 16:
+            return m_16Pool.pop(ptr);
+        default:
+            return false;
+        }
+    }
+
+    void clear();
+
+private:
+    QReadWriteLock m_cacheLock;
+    KisLocklessStack<quint8*> m_4Pool;
+    KisLocklessStack<quint8*> m_8Pool;
+    KisLocklessStack<quint8*> m_16Pool;
+};
+
+
 /**
  * Stores actual tile's data
  */
@@ -137,7 +188,7 @@
      *
      * Effectively equivalent to: (mementoed() && numUsers() <= 1)
      */
-     inline bool historical() const;
+    inline bool historical() const;
 
     /**
      * Used for swapping purposes only.
@@ -202,7 +253,8 @@
      * Iterator that points to a position in the list
      * where the tile data is stored
      */
-    KisTileDataListIterator m_listIterator;
+//    KisTileDataListIterator m_listIterator;
+    int m_tileNumber = -1;
 
 private:
     /**
@@ -264,6 +316,8 @@
     //qint32 m_timeStamp;
 
     KisTileDataStore *m_store;
+    static SimpleCache m_cache;
+
 public:
     static const qint32 WIDTH;
     static const qint32 HEIGHT;
diff --git a/libs/image/tiles3/kis_tile_data_store.h b/libs/image/tiles3/kis_tile_data_store.h
--- a/libs/image/tiles3/kis_tile_data_store.h
+++ b/libs/image/tiles3/kis_tile_data_store.h
@@ -26,6 +26,7 @@
 #include "kis_tile_data_pooler.h"
 #include "swap/kis_tile_data_swapper.h"
 #include "swap/kis_swapped_data_store.h"
+#include "3rdparty/lock_free_map/concurrent_map.h"
 
 class KisTileDataStoreIterator;
 class KisTileDataStoreReverseIterator;
@@ -59,26 +60,30 @@
      * Returns total number of tiles present: in memory
      * or in a swap file
      */
-    inline qint32 numTiles() const {
-        return m_numTiles + m_swappedStore.numTiles();
+    inline qint32 numTiles() const
+    {
+        return m_numTiles.loadAcquire() + m_swappedStore.numTiles();
     }
 
     /**
      * Returns the number of tiles present in memory only
      */
-    inline qint32 numTilesInMemory() const {
-        return m_numTiles;
+    inline qint32 numTilesInMemory() const
+    {
+        return m_numTiles.loadAcquire();
     }
 
-    inline void checkFreeMemory() {
+    inline void checkFreeMemory()
+    {
         m_swapper.checkFreeMemory();
     }
 
     /**
      * \see m_memoryMetric
      */
-    inline qint64 memoryMetric() const {
-        return m_memoryMetric;
+    inline qint64 memoryMetric() const
+    {
+        return m_memoryMetric.loadAcquire();
     }
 
     KisTileDataStoreIterator* beginIteration();
@@ -90,12 +95,14 @@
     KisTileDataStoreClockIterator* beginClockIteration();
     void endIteration(KisTileDataStoreClockIterator* iterator);
 
-    inline KisTileData* createDefaultTileData(qint32 pixelSize, const quint8 *defPixel) {
+    inline KisTileData* createDefaultTileData(qint32 pixelSize, const quint8 *defPixel)
+    {
         return allocTileData(pixelSize, defPixel);
     }
 
     // Called by The Memento Manager after every commit
-    inline void kickPooler() {
+    inline void kickPooler()
+    {
         m_pooler.kick();
 
         //FIXME: maybe, rename a function?
@@ -159,18 +166,17 @@
     friend class KisTileDataPoolerTest;
     KisSwappedDataStore m_swappedStore;
 
-    KisTileDataListIterator m_clockIterator;
-
-    QMutex m_listLock;
-    KisTileDataList m_tileDataList;
-    qint32 m_numTiles;
-
     /**
      * This metric is used for computing the volume
      * of memory occupied by tile data objects.
      * metric = num_bytes / (KisTileData::WIDTH * KisTileData::HEIGHT)
      */
-    qint64 m_memoryMetric;
+    QAtomicInt m_numTiles;
+    QAtomicInt m_memoryMetric;
+    QAtomicInt m_counter;
+    QAtomicInt m_clockIndex;
+    ConcurrentMap<int, KisTileData*> m_tileDataMap;
+    QReadWriteLock m_iteratorLock;
 };
 
 template<typename T>
diff --git a/libs/image/tiles3/kis_tile_data_store.cc b/libs/image/tiles3/kis_tile_data_store.cc
--- a/libs/image/tiles3/kis_tile_data_store.cc
+++ b/libs/image/tiles3/kis_tile_data_store.cc
@@ -70,9 +70,10 @@
     : m_pooler(this),
       m_swapper(this),
       m_numTiles(0),
-      m_memoryMetric(0)
+      m_memoryMetric(0),
+      m_counter(1),
+      m_clockIndex(1)
 {
-    m_clockIterator = m_tileDataList.end();
     m_pooler.start();
     m_swapper.start();
 }
@@ -82,10 +83,10 @@
     m_pooler.terminatePooler();
     m_swapper.terminateSwapper();
 
-    if(numTiles() > 0) {
-         errKrita << "Warning: some tiles have leaked:";
-         errKrita << "\tTiles in memory:" << numTilesInMemory() << "\n"
-                    << "\tTotal tiles:" << numTiles();
+    if (numTiles() > 0) {
+        errKrita << "Warning: some tiles have leaked:";
+        errKrita << "\tTiles in memory:" << numTilesInMemory() << "\n"
+                 << "\tTotal tiles:" << numTiles();
     }
 }
 
@@ -102,7 +103,7 @@
         m_pooler.forceUpdateMemoryStats();
     }
 
-    QMutexLocker lock(&m_listLock);
+    QReadLocker lock(&m_iteratorLock);
 
     MemoryStatistics stats;
 
@@ -121,34 +122,37 @@
 
 inline void KisTileDataStore::registerTileDataImp(KisTileData *td)
 {
-    td->m_listIterator = m_tileDataList.insert(m_tileDataList.end(), td);
-    m_numTiles++;
+    int index = m_counter.fetchAndAddOrdered(1);
+    td->m_tileNumber = index;
+    m_tileDataMap.assign(index, td);
+    m_numTiles.ref();
     m_memoryMetric += td->pixelSize();
 }
 
 void KisTileDataStore::registerTileData(KisTileData *td)
 {
-    QMutexLocker lock(&m_listLock);
+    QReadLocker lock(&m_iteratorLock);
     registerTileDataImp(td);
 }
 
 inline void KisTileDataStore::unregisterTileDataImp(KisTileData *td)
 {
-    KisTileDataListIterator tempIterator = td->m_listIterator;
-
-    if(m_clockIterator == tempIterator) {
-        m_clockIterator = tempIterator + 1;
+    if (m_clockIndex == td->m_tileNumber) {
+        do {
+            m_clockIndex.ref();
+        } while (!m_tileDataMap.get(m_clockIndex.loadAcquire()) && m_clockIndex < m_counter);
     }
 
-    td->m_listIterator = m_tileDataList.end();
-    m_tileDataList.erase(tempIterator);
-    m_numTiles--;
+    int index = td->m_tileNumber;
+    td->m_tileNumber = -1;
+    m_tileDataMap.erase(index);
+    m_numTiles.deref();
     m_memoryMetric -= td->pixelSize();
 }
 
 void KisTileDataStore::unregisterTileData(KisTileData *td)
 {
-    QMutexLocker lock(&m_listLock);
+    QReadLocker lock(&m_iteratorLock);
     unregisterTileDataImp(td);
 }
 
@@ -184,18 +188,17 @@
 
     DEBUG_FREE_ACTION(td);
 
-    m_listLock.lock();
+    m_iteratorLock.lockForRead();
     td->m_swapLock.lockForWrite();
 
-    if(!td->data()) {
+    if (!td->data()) {
         m_swappedStore.forgetTileData(td);
-    }
-    else {
+    } else {
         unregisterTileDataImp(td);
     }
 
     td->m_swapLock.unlock();
-    m_listLock.unlock();
+    m_iteratorLock.unlock();
 
     delete td;
 }
@@ -207,14 +210,14 @@
 
     td->m_swapLock.lockForRead();
 
-    while(!td->data()) {
+    while (!td->data()) {
         td->m_swapLock.unlock();
 
         /**
          * The order of this heavy locking is very important.
          * Change it only in case, you really know what you are doing.
          */
-        m_listLock.lock();
+        m_iteratorLock.lockForRead();
 
         /**
          * If someone has managed to load the td from swap, then, most
@@ -229,7 +232,7 @@
          * m_listLock.
          */
 
-        if(!td->data()) {
+        if (!td->data()) {
             td->m_swapLock.lockForWrite();
 
             m_swappedStore.swapInTileData(td);
@@ -238,7 +241,7 @@
             td->m_swapLock.unlock();
         }
 
-        m_listLock.unlock();
+        m_iteratorLock.unlock();
 
         /**
          * <-- In theory, livelock is possible here...
@@ -255,9 +258,9 @@
      */
 
     bool result = false;
-    if(!td->m_swapLock.tryLockForWrite()) return result;
+    if (!td->m_swapLock.tryLockForWrite()) return result;
 
-    if(td->data()) {
+    if (td->data()) {
         unregisterTileDataImp(td);
         if (m_swappedStore.trySwapOutTileData(td)) {
             result = true;
@@ -273,43 +276,47 @@
 
 KisTileDataStoreIterator* KisTileDataStore::beginIteration()
 {
-    m_listLock.lock();
-    return new KisTileDataStoreIterator(m_tileDataList, this);
+    m_iteratorLock.lockForWrite();
+    return new KisTileDataStoreIterator(m_tileDataMap, this);
 }
 void KisTileDataStore::endIteration(KisTileDataStoreIterator* iterator)
 {
     delete iterator;
-    m_listLock.unlock();
+    m_iteratorLock.unlock();
 }
 
 KisTileDataStoreReverseIterator* KisTileDataStore::beginReverseIteration()
 {
-    m_listLock.lock();
-    return new KisTileDataStoreReverseIterator(m_tileDataList, this);
+    m_iteratorLock.lockForWrite();
+    return new KisTileDataStoreReverseIterator(m_tileDataMap, this);
 }
 void KisTileDataStore::endIteration(KisTileDataStoreReverseIterator* iterator)
 {
     delete iterator;
-    m_listLock.unlock();
+    m_iteratorLock.unlock();
     DEBUG_REPORT_PRECLONE_EFFICIENCY();
 }
 
 KisTileDataStoreClockIterator* KisTileDataStore::beginClockIteration()
 {
-    m_listLock.lock();
-    return new KisTileDataStoreClockIterator(m_clockIterator, m_tileDataList, this);
+    m_iteratorLock.lockForWrite();
+    return new KisTileDataStoreClockIterator(m_tileDataMap, m_clockIndex.loadAcquire(), this);
 }
 void KisTileDataStore::endIteration(KisTileDataStoreClockIterator* iterator)
 {
-    m_clockIterator = iterator->getFinalPosition();
+    m_clockIndex = iterator->getFinalPosition();
     delete iterator;
-    m_listLock.unlock();
+    m_iteratorLock.unlock();
 }
 
 void KisTileDataStore::debugPrintList()
 {
-    KisTileData *item;
-    Q_FOREACH (item, m_tileDataList) {
+    QWriteLocker l(&m_iteratorLock);
+    ConcurrentMap<int, KisTileData*>::Iterator iter(m_tileDataMap);
+    KisTileData *item = 0;
+
+    while (iter.isValid()) {
+        item = iter.getValue();
         dbgTiles << "-------------------------\n"
                  << "TileData:\t\t\t" << item
                  << "\n  refCount:\t" << item->m_refCount;
@@ -320,7 +327,7 @@
 {
     KisTileDataStoreIterator* iter = beginIteration();
     KisTileData *item;
-    while(iter->hasNext()) {
+    while (iter->hasNext()) {
         item = iter->next();
         iter->trySwapOut(item);
     }
@@ -333,20 +340,22 @@
 
 void KisTileDataStore::debugClear()
 {
-    QMutexLocker lock(&m_listLock);
+    QWriteLocker l(&m_iteratorLock);
+    ConcurrentMap<int, KisTileData*>::Iterator iter(m_tileDataMap);
 
-    Q_FOREACH (KisTileData *item, m_tileDataList) {
-        delete item;
+    while (iter.isValid()) {
+        delete iter.getValue();
+        iter.next();
     }
 
-    m_tileDataList.clear();
-    m_clockIterator = m_tileDataList.end();
-
+    m_counter = 1;
+    m_clockIndex = 1;
     m_numTiles = 0;
     m_memoryMetric = 0;
 }
 
-void KisTileDataStore::testingRereadConfig() {
+void KisTileDataStore::testingRereadConfig()
+{
     m_pooler.testingRereadConfig();
     m_swapper.testingRereadConfig();
     kickPooler();
diff --git a/libs/image/tiles3/kis_tile_data_store_iterators.h b/libs/image/tiles3/kis_tile_data_store_iterators.h
--- a/libs/image/tiles3/kis_tile_data_store_iterators.h
+++ b/libs/image/tiles3/kis_tile_data_store_iterators.h
@@ -18,6 +18,9 @@
 #ifndef KIS_TILE_DATA_STORE_ITERATORS_H_
 #define KIS_TILE_DATA_STORE_ITERATORS_H_
 
+#include "kis_tile_data.h"
+#include "kis_debug.h"
+
 /**
  * KisTileDataStoreIterator,
  * KisTileDataStoreReverseIterator,
@@ -35,140 +38,124 @@
 class KisTileDataStoreIterator
 {
 public:
-    KisTileDataStoreIterator(KisTileDataList &list, KisTileDataStore *store)
-        : m_list(list),
+    KisTileDataStoreIterator(ConcurrentMap<int, KisTileData*> &map, KisTileDataStore *store)
+        : m_map(map),
           m_store(store)
     {
-        m_iterator = m_list.begin();
-        m_end = m_list.end();
+        m_iterator.setMap(m_map);
     }
 
-    inline KisTileData* peekNext() {
-        return *m_iterator;
+    inline KisTileData* peekNext()
+    {
+        return m_iterator.getValue();
     }
 
-    inline KisTileData* next() {
-        return *(m_iterator++);
+    inline KisTileData* next()
+    {
+        KisTileData *current = m_iterator.getValue();
+        m_iterator.next();
+        return current;
     }
 
-    inline bool hasNext() const {
-        return m_iterator != m_end;
+    inline bool hasNext() const
+    {
+        return m_iterator.isValid();
     }
 
-    inline bool trySwapOut(KisTileData *td) {
-        if(td->m_listIterator == m_iterator)
-            m_iterator++;
+    inline bool trySwapOut(KisTileData *td)
+    {
+        if (td == m_iterator.getValue()) {
+            m_iterator.next();
+        }
 
         return m_store->trySwapTileData(td);
     }
 
 private:
-    KisTileDataList &m_list;
-    KisTileDataListIterator m_iterator;
-    KisTileDataListIterator m_end;
+    ConcurrentMap<int, KisTileData*> &m_map;
+    ConcurrentMap<int, KisTileData*>::Iterator m_iterator;
     KisTileDataStore *m_store;
 };
 
-class KisTileDataStoreReverseIterator
+class KisTileDataStoreReverseIterator : public KisTileDataStoreIterator
 {
 public:
-    KisTileDataStoreReverseIterator(KisTileDataList &list, KisTileDataStore *store)
-        : m_list(list),
-          m_store(store)
+    KisTileDataStoreReverseIterator(ConcurrentMap<int, KisTileData*> &map, KisTileDataStore *store)
+        : KisTileDataStoreIterator(map, store)
     {
-        m_iterator = m_list.end();
-        m_begin = m_list.begin();
     }
-
-    inline KisTileData* peekNext() {
-        return *(m_iterator-1);
-    }
-
-    inline KisTileData* next() {
-        return *(--m_iterator);
-    }
-
-    inline bool hasNext() const {
-        return m_iterator != m_begin;
-    }
-
-    inline bool trySwapOut(KisTileData *td) {
-        if(td->m_listIterator == m_iterator)
-            m_iterator++;
-
-        return m_store->trySwapTileData(td);
-    }
-
-private:
-    KisTileDataList &m_list;
-    KisTileDataListIterator m_iterator;
-    KisTileDataListIterator m_begin;
-    KisTileDataStore *m_store;
 };
 
 class KisTileDataStoreClockIterator
 {
 public:
-    KisTileDataStoreClockIterator(KisTileDataListIterator startItem, KisTileDataList &list, KisTileDataStore *store)
-        : m_list(list),
+    KisTileDataStoreClockIterator(ConcurrentMap<int, KisTileData*> &map,
+                                  int startIndex,
+                                  KisTileDataStore *store)
+        : m_map(map),
           m_store(store)
     {
-        m_end = m_list.end();
+        m_iterator.setMap(m_map);
+        m_startItem = m_map.get(startIndex);
 
-        if(startItem == m_list.begin() ||
-           startItem == m_end) {
-            m_iterator = m_list.begin();
-            m_startItem = m_end;
+        if (m_iterator.getValue() == m_startItem || !m_startItem) {
             m_endReached = true;
-        }
-        else  {
-            m_startItem = startItem;
-            m_iterator = startItem;
+        } else {
+            while (m_iterator.getValue() != m_startItem) {
+                m_iterator.next();
+            }
             m_endReached = false;
         }
     }
 
-    inline KisTileData* peekNext() {
-        if(m_iterator == m_end) {
-            m_iterator = m_list.begin();
+    inline KisTileData* peekNext()
+    {
+        if (!m_iterator.isValid()) {
+            m_iterator.setMap(m_map);
             m_endReached = true;
         }
 
-        return *m_iterator;
+        return m_iterator.getValue();
     }
 
-    inline KisTileData* next() {
-        if(m_iterator == m_end) {
-            m_iterator = m_list.begin();
+    inline KisTileData* next()
+    {
+        if (!m_iterator.isValid()) {
+            m_iterator.setMap(m_map);
             m_endReached = true;
         }
 
-        return *(m_iterator++);
+        KisTileData *current = m_iterator.getValue();
+        m_iterator.next();
+        return current;
     }
 
-    inline bool hasNext() const {
-        return !(m_endReached && m_iterator == m_startItem);
+    inline bool hasNext() const
+    {
+        return !(m_endReached && m_iterator.getValue() == m_startItem);
     }
 
-    inline bool trySwapOut(KisTileData *td) {
-        if(td->m_listIterator == m_iterator)
-            m_iterator++;
+    inline bool trySwapOut(KisTileData *td)
+    {
+        if (td == m_iterator.getValue()) {
+            m_iterator.next();
+        }
 
         return m_store->trySwapTileData(td);
     }
 
 private:
     friend class KisTileDataStore;
-    inline KisTileDataListIterator getFinalPosition() {
-        return m_iterator;
+    inline int getFinalPosition()
+    {
+        return m_iterator.getValue()->m_tileNumber;
     }
 
 private:
-    KisTileDataList &m_list;
+    ConcurrentMap<int, KisTileData*> &m_map;
+    ConcurrentMap<int, KisTileData*>::Iterator m_iterator;
+    KisTileData *m_startItem;
     bool m_endReached;
-    KisTileDataListIterator m_iterator;
-    KisTileDataListIterator m_startItem;
-    KisTileDataListIterator m_end;
     KisTileDataStore *m_store;
 };