diff --git a/libs/image/CMakeLists.txt b/libs/image/CMakeLists.txt
index dbddc9b..434e01a 100644
--- a/libs/image/CMakeLists.txt
+++ b/libs/image/CMakeLists.txt
@@ -41,6 +41,7 @@ set(kritaimage_LIB_SRCS
     tiles3/kis_tile_data_store.cc
     tiles3/kis_tile_data_pooler.cc
     tiles3/kis_tiled_data_manager.cc
+    tiles3/KisTiledExtentManager.cpp
     tiles3/kis_memento_manager.cc
     tiles3/kis_hline_iterator.cpp
     tiles3/kis_vline_iterator.cpp
diff --git a/libs/image/tiles3/KisTiledExtentManager.cpp b/libs/image/tiles3/KisTiledExtentManager.cpp
new file mode 100644
index 0000000..9a71e0a
--- /dev/null
+++ b/libs/image/tiles3/KisTiledExtentManager.cpp
@@ -0,0 +1,152 @@
+/*
+ *  Copyright (c) 2017 Dmitry Kazakov <dimula73@gmail.com>
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "KisTiledExtentManager.h"
+
+#include <QMutex>
+#include <QVector>
+#include "kis_tile_data_interface.h"
+#include "kis_assert.h"
+#include "kis_global.h"
+
+namespace {
+
+inline bool addTileToMap(int index, QMap<int, int> *map)
+{
+    bool needsUpdateExtent = false;
+
+    auto it = map->find(index);
+
+    if (it == map->end()) {
+        map->insert(index, 1);
+        needsUpdateExtent = true;
+    } else {
+        KIS_ASSERT_RECOVER_NOOP(*it > 0);
+        (*it)++;
+    }
+
+    return needsUpdateExtent;
+}
+
+inline bool removeTileFromMap(int index, QMap<int, int> *map)
+{
+    bool needsUpdateExtent = false;
+
+    auto it = map->find(index);
+
+    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 (*it <= 0) {
+            map->erase(it);
+            needsUpdateExtent = true;
+        }
+    }
+
+    return needsUpdateExtent;
+}
+
+
+}
+
+KisTiledExtentManager::KisTiledExtentManager()
+{
+}
+
+void KisTiledExtentManager::notifyTileAdded(int col, int row)
+{
+    QMutexLocker l(&m_mutex);
+
+    bool needsUpdateExtent = false;
+
+    needsUpdateExtent |= addTileToMap(col, &m_colMap);
+    needsUpdateExtent |= addTileToMap(row, &m_rowMap);
+
+    if (needsUpdateExtent) {
+        updateExtent();
+    }
+}
+
+void KisTiledExtentManager::notifyTileRemoved(int col, int row)
+{
+    QMutexLocker l(&m_mutex);
+
+    bool needsUpdateExtent = false;
+
+    needsUpdateExtent |= removeTileFromMap(col, &m_colMap);
+    needsUpdateExtent |= removeTileFromMap(row, &m_rowMap);
+
+    if (needsUpdateExtent) {
+        updateExtent();
+    }
+}
+
+void KisTiledExtentManager::replaceTileStats(const QVector<QPoint> &indexes)
+{
+    QMutexLocker l(&m_mutex);
+
+    m_colMap.clear();
+    m_rowMap.clear();
+
+    Q_FOREACH (const QPoint &index, indexes) {
+        addTileToMap(index.x(), &m_colMap);
+        addTileToMap(index.y(), &m_rowMap);
+    }
+
+    updateExtent();
+}
+
+void KisTiledExtentManager::clear()
+{
+    QMutexLocker l(&m_mutex);
+
+    m_colMap.clear();
+    m_rowMap.clear();
+    m_currentExtent = QRect(qint32_MAX, qint32_MAX, 0, 0);
+
+}
+
+QRect KisTiledExtentManager::extent() const
+{
+    QMutexLocker l(&m_mutex);
+    return m_currentExtent;
+}
+
+void KisTiledExtentManager::updateExtent()
+{
+    KIS_ASSERT_RECOVER_RETURN(m_colMap.isEmpty() == m_rowMap.isEmpty());
+
+    // here we check for only one map for efficiency reasons
+    if (m_colMap.isEmpty()) {
+        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;
+
+        m_currentExtent =
+            QRect(minX, minY,
+                  maxPlusOneX - minX,
+                  maxPlusOneY - minY);
+    }
+}
+
diff --git a/libs/image/tiles3/KisTiledExtentManager.h b/libs/image/tiles3/KisTiledExtentManager.h
new file mode 100644
index 0000000..b4fa94b
--- /dev/null
+++ b/libs/image/tiles3/KisTiledExtentManager.h
@@ -0,0 +1,51 @@
+/*
+ *  Copyright (c) 2017 Dmitry Kazakov <dimula73@gmail.com>
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef KISTILEDEXTENTMANAGER_H
+#define KISTILEDEXTENTMANAGER_H
+
+#include <QMutex>
+#include <QMap>
+#include <QRect>
+#include "kritaimage_export.h"
+
+
+class KRITAIMAGE_EXPORT KisTiledExtentManager
+{
+public:
+    KisTiledExtentManager();
+
+    void notifyTileAdded(int col, int row);
+    void notifyTileRemoved(int col, int row);
+    void replaceTileStats(const QVector<QPoint> &indexes);
+
+    void clear();
+
+    QRect extent() const;
+
+private:
+    void updateExtent();
+
+private:
+    mutable QMutex m_mutex;
+    QMap<int, int> m_colMap;
+    QMap<int, int> m_rowMap;
+    QRect m_currentExtent;
+};
+
+#endif // KISTILEDEXTENTMANAGER_H
diff --git a/libs/image/tiles3/kis_tile_hash_table.h b/libs/image/tiles3/kis_tile_hash_table.h
index 7e8f758..6d81b78 100644
--- a/libs/image/tiles3/kis_tile_hash_table.h
+++ b/libs/image/tiles3/kis_tile_hash_table.h
@@ -81,8 +81,8 @@ public:
      */
     TileTypeSP getReadOnlyTileLazy(qint32 col, qint32 row);
     void addTile(TileTypeSP tile);
-    void deleteTile(TileTypeSP tile);
-    void deleteTile(qint32 col, qint32 row);
+    bool deleteTile(TileTypeSP tile);
+    bool deleteTile(qint32 col, qint32 row);
 
     void clear();
 
diff --git a/libs/image/tiles3/kis_tile_hash_table_p.h b/libs/image/tiles3/kis_tile_hash_table_p.h
index 2adaeda..4afda90 100644
--- a/libs/image/tiles3/kis_tile_hash_table_p.h
+++ b/libs/image/tiles3/kis_tile_hash_table_p.h
@@ -285,7 +285,7 @@ void KisTileHashTableTraits<T>::addTile(TileTypeSP tile)
 }
 
 template<class T>
-void KisTileHashTableTraits<T>::deleteTile(qint32 col, qint32 row)
+bool KisTileHashTableTraits<T>::deleteTile(qint32 col, qint32 row)
 {
     const qint32 idx = calculateHash(col, row);
 
@@ -296,12 +296,13 @@ void KisTileHashTableTraits<T>::deleteTile(qint32 col, qint32 row)
     //if(tile)
     //    delete tile;
 
+    return bool(tile);
 }
 
 template<class T>
-void KisTileHashTableTraits<T>::deleteTile(TileTypeSP tile)
+bool KisTileHashTableTraits<T>::deleteTile(TileTypeSP tile)
 {
-    deleteTile(tile->col(), tile->row());
+    return deleteTile(tile->col(), tile->row());
 }
 
 template<class T>
diff --git a/libs/image/tiles3/kis_tiled_data_manager.cc b/libs/image/tiles3/kis_tiled_data_manager.cc
index df29afc..b83670f 100644
--- a/libs/image/tiles3/kis_tiled_data_manager.cc
+++ b/libs/image/tiles3/kis_tiled_data_manager.cc
@@ -52,11 +52,6 @@ KisTiledDataManager::KisTiledDataManager(quint32 pixelSize,
     m_pixelSize = pixelSize;
     m_defaultPixel = new quint8[m_pixelSize];
     setDefaultPixel(defaultPixel);
-
-    m_extentMinX = qint32_MAX;
-    m_extentMinY = qint32_MAX;
-    m_extentMaxX = qint32_MIN;
-    m_extentMaxY = qint32_MIN;
 }
 
 KisTiledDataManager::KisTiledDataManager(const KisTiledDataManager &dm)
@@ -76,11 +71,7 @@ KisTiledDataManager::KisTiledDataManager(const KisTiledDataManager &dm)
      * has already been made shared in m_hashTable(dm->m_hashTable)
      */
     memcpy(m_defaultPixel, dm.m_defaultPixel, m_pixelSize);
-
-    m_extentMinX = dm.m_extentMinX;
-    m_extentMinY = dm.m_extentMinY;
-    m_extentMaxX = dm.m_extentMaxX;
-    m_extentMaxY = dm.m_extentMaxY;
+    recalculateExtent();
 }
 
 KisTiledDataManager::~KisTiledDataManager()
@@ -280,8 +271,6 @@ wrongString:
 
 void KisTiledDataManager::purge(const QRect& area)
 {
-    QWriteLocker locker(&m_lock);
-
     QList<KisTileSP> tilesToDelete;
     {
         const qint32 tileDataSize = KisTileData::HEIGHT * KisTileData::WIDTH * pixelSize();
@@ -306,10 +295,9 @@ void KisTiledDataManager::purge(const QRect& area)
         tileData->unblockSwapping();
     }
     Q_FOREACH (KisTileSP tile, tilesToDelete) {
+        m_extentManager.notifyTileRemoved(tile->col(), tile->row());
         m_hashTable->deleteTile(tile);
     }
-
-    recalculateExtent();
 }
 
 quint8* KisTiledDataManager::duplicatePixel(qint32 num, const quint8 *pixel)
@@ -327,8 +315,6 @@ quint8* KisTiledDataManager::duplicatePixel(qint32 num, const quint8 *pixel)
 
 void KisTiledDataManager::clear(QRect clearRect, const quint8 *clearPixel)
 {
-    QWriteLocker locker(&m_lock);
-
     if (clearPixel == 0)
         clearPixel = m_defaultPixel;
 
@@ -348,7 +334,7 @@ void KisTiledDataManager::clear(QRect clearRect, const quint8 *clearPixel)
     }
 
     if (pixelBytesAreDefault) {
-        clearRect &= extentImpl();
+        clearRect &= m_extentManager.extent();
     }
 
     qint32 firstColumn = xToCol(clearRect.left());
@@ -373,8 +359,6 @@ void KisTiledDataManager::clear(QRect clearRect, const quint8 *clearPixel)
         td->acquire();
     }
 
-    bool needsRecalculateExtent = false;
-
     for (qint32 row = firstRow; row <= lastRow; ++row) {
         for (qint32 column = firstColumn; column <= lastColumn; ++column) {
 
@@ -384,19 +368,18 @@ void KisTiledDataManager::clear(QRect clearRect, const quint8 *clearPixel)
 
             if (clearTileRect == tileRect) {
                  // Clear whole tile
-                 m_hashTable->deleteTile(column, row);
-
-                 if (!needsRecalculateExtent &&
-                     (m_extentMinX == tileRect.left() || m_extentMaxX == tileRect.right() ||
-                      m_extentMinY == tileRect.top() || m_extentMaxY == tileRect.bottom())) {
+                 const bool wasDeleted =
+                     m_hashTable->deleteTile(column, row);
 
-                     needsRecalculateExtent = true;
+                 if (wasDeleted) {
+                     m_extentManager.notifyTileRemoved(column, row);
                  }
 
+
                  if (!pixelBytesAreDefault) {
                      KisTileSP clearedTile = KisTileSP(new KisTile(column, row, td, m_mementoManager));
                      m_hashTable->addTile(clearedTile);
-                     updateExtent(column, row);
+                     m_extentManager.notifyTileAdded(column, row);
                  }
             } else {
                 const qint32 lineSize = clearTileRect.width() * pixelSize;
@@ -425,10 +408,6 @@ void KisTiledDataManager::clear(QRect clearRect, const quint8 *clearPixel)
         }
     }
 
-    if (needsRecalculateExtent) {
-        recalculateExtent();
-    }
-
     if (td) td->release();
     delete[] clearPixelData;
 }
@@ -452,22 +431,14 @@ void KisTiledDataManager::clear(qint32 x, qint32 y, qint32 w, qint32 h, quint8 c
 
 void KisTiledDataManager::clear()
 {
-    QWriteLocker locker(&m_lock);
-
     m_hashTable->clear();
-
-    m_extentMinX = qint32_MAX;
-    m_extentMinY = qint32_MAX;
-    m_extentMaxX = qint32_MIN;
-    m_extentMaxY = qint32_MIN;
+    m_extentManager.clear();
 }
 
 
 template<bool useOldSrcData>
 void KisTiledDataManager::bitBltImpl(KisTiledDataManager *srcDM, const QRect &rect)
 {
-    QWriteLocker locker(&m_lock);
-
     if (rect.isEmpty()) return;
 
     const qint32 pixelSize = this->pixelSize();
@@ -493,7 +464,8 @@ void KisTiledDataManager::bitBltImpl(KisTiledDataManager *srcDM, const QRect &re
 
             if (cloneTileRect == tileRect) {
                  // Clone whole tile
-                 m_hashTable->deleteTile(column, row);
+                 const bool wasDeleted =
+                     m_hashTable->deleteTile(column, row);
 
                  srcTile->lockForRead();
                  KisTileData *td = srcTile->tileData();
@@ -501,7 +473,10 @@ void KisTiledDataManager::bitBltImpl(KisTiledDataManager *srcDM, const QRect &re
                  srcTile->unlock();
 
                  m_hashTable->addTile(clonedTile);
-                 updateExtent(column, row);
+
+                 if (!wasDeleted) {
+                     m_extentManager.notifyTileAdded(column, row);
+                 }
             } else {
                 const qint32 lineSize = cloneTileRect.width() * pixelSize;
                 qint32 rowsRemaining = cloneTileRect.height();
@@ -531,8 +506,6 @@ void KisTiledDataManager::bitBltImpl(KisTiledDataManager *srcDM, const QRect &re
 template<bool useOldSrcData>
 void KisTiledDataManager::bitBltRoughImpl(KisTiledDataManager *srcDM, const QRect &rect)
 {
-    QWriteLocker locker(&m_lock);
-
     if (rect.isEmpty()) return;
 
     qint32 firstColumn = xToCol(rect.left());
@@ -554,7 +527,8 @@ void KisTiledDataManager::bitBltRoughImpl(KisTiledDataManager *srcDM, const QRec
                 srcDM->getOldTile(column, row) :
                 srcDM->getTile(column, row, false);
 
-            m_hashTable->deleteTile(column, row);
+            const bool wasDeleted =
+                m_hashTable->deleteTile(column, row);
 
             srcTile->lockForRead();
             KisTileData *td = srcTile->tileData();
@@ -562,7 +536,10 @@ void KisTiledDataManager::bitBltRoughImpl(KisTiledDataManager *srcDM, const QRec
             srcTile->unlock();
 
             m_hashTable->addTile(clonedTile);
-            updateExtent(column, row);
+
+            if (!wasDeleted) {
+                m_extentManager.notifyTileAdded(column, row);
+            }
         }
     }
 }
@@ -601,8 +578,6 @@ void KisTiledDataManager::setExtent(QRect newRect)
     // that is handled by the autoextending automatically
     if (newRect.contains(oldRect)) return;
 
-    QWriteLocker locker(&m_lock);
-
     KisTileSP tile;
     QRect tileRect;
     {
@@ -637,51 +612,28 @@ void KisTiledDataManager::setExtent(QRect newRect)
                 tile->unlock();
                 iter.next();
             } else {
+                m_extentManager.notifyTileRemoved(tile->col(), tile->row());
                 iter.deleteCurrent();
             }
         }
     }
-
-    recalculateExtent();
 }
 
 void KisTiledDataManager::recalculateExtent()
 {
-    m_extentMinX = qint32_MAX;
-    m_extentMinY = qint32_MAX;
-    m_extentMaxX = qint32_MIN;
-    m_extentMaxY = qint32_MIN;
+    QVector<QPoint> indexes;
 
-    KisTileHashTableConstIterator iter(m_hashTable);
-    KisTileSP tile;
+    {
+        KisTileHashTableConstIterator iter(m_hashTable);
+        KisTileSP tile;
 
-    while ((tile = iter.tile())) {
-        updateExtent(tile->col(), tile->row());
-        iter.next();
+        while ((tile = iter.tile())) {
+            indexes << QPoint(tile->col(), tile->row());
+            iter.next();
+        }
     }
-}
-
-void KisTiledDataManager::updateExtent(qint32 col, qint32 row)
-{
-    const qint32 tileMinX = col * KisTileData::WIDTH;
-    const qint32 tileMinY = row * KisTileData::HEIGHT;
-    const qint32 tileMaxX = tileMinX + KisTileData::WIDTH - 1;
-    const qint32 tileMaxY = tileMinY + KisTileData::HEIGHT - 1;
 
-    m_extentMinX = qMin(m_extentMinX, tileMinX);
-    m_extentMaxX = qMax(m_extentMaxX, tileMaxX);
-    m_extentMinY = qMin(m_extentMinY, tileMinY);
-    m_extentMaxY = qMax(m_extentMaxY, tileMaxY);
-}
-
-QRect KisTiledDataManager::extentImpl() const
-{
-    qint32 x = m_extentMinX;
-    qint32 y = m_extentMinY;
-    qint32 w = (m_extentMaxX >= m_extentMinX) ? m_extentMaxX - m_extentMinX + 1 : 0;
-    qint32 h = (m_extentMaxY >= m_extentMinY) ? m_extentMaxY - m_extentMinY + 1 : 0;
-
-    return QRect(x, y, w, h);
+    m_extentManager.replaceTileStats(indexes);
 }
 
 void KisTiledDataManager::extent(qint32 &x, qint32 &y, qint32 &w, qint32 &h) const
@@ -692,8 +644,7 @@ void KisTiledDataManager::extent(qint32 &x, qint32 &y, qint32 &w, qint32 &h) con
 
 QRect KisTiledDataManager::extent() const
 {
-    QReadLocker locker(&m_lock);
-    return extentImpl();
+    return m_extentManager.extent();
 }
 
 QRegion KisTiledDataManager::region() const
@@ -712,7 +663,6 @@ QRegion KisTiledDataManager::region() const
 
 void KisTiledDataManager::setPixel(qint32 x, qint32 y, const quint8 * data)
 {
-    QWriteLocker locker(&m_lock);
     KisTileDataWrapper tw(this, x, y, KisTileDataWrapper::WRITE);
     memcpy(tw.data(), data, pixelSize());
 }
diff --git a/libs/image/tiles3/kis_tiled_data_manager.h b/libs/image/tiles3/kis_tiled_data_manager.h
index 25f9dd8..964fc3e 100644
--- a/libs/image/tiles3/kis_tiled_data_manager.h
+++ b/libs/image/tiles3/kis_tiled_data_manager.h
@@ -32,7 +32,7 @@
 #include "kis_tile_hash_table.h"
 #include "kis_memento_manager.h"
 #include "kis_memento.h"
-
+#include "KisTiledExtentManager.h"
 
 class KisTiledDataManager;
 typedef KisSharedPtr<KisTiledDataManager> KisTiledDataManagerSP;
@@ -109,8 +109,9 @@ public:
         if (writable) {
             bool newTile;
             KisTileSP tile = m_hashTable->getTileLazy(col, row, newTile);
-            if (newTile)
-                updateExtent(tile->col(), tile->row());
+            if (newTile) {
+                m_extentManager.notifyTileAdded(col, row);
+            }
             return tile;
 
         } else {
@@ -319,14 +320,7 @@ private:
     KisMementoManager *m_mementoManager;
     quint8* m_defaultPixel;
     qint32 m_pixelSize;
-
-    /**
-     * Extents stuff
-     */
-    qint32 m_extentMinX;
-    qint32 m_extentMaxX;
-    qint32 m_extentMinY;
-    qint32 m_extentMaxY;
+    KisTiledExtentManager m_extentManager;
 
     mutable QReadWriteLock m_lock;
 
@@ -341,14 +335,11 @@ private:
 private:
     void setDefaultPixelImpl(const quint8 *defPixel);
 
-    QRect extentImpl() const;
-
     bool writeTilesHeader(KisPaintDeviceWriter &store, quint32 numTiles);
     bool processTilesHeader(QIODevice *stream, quint32 &numTiles);
 
     qint32 divideRoundDown(qint32 x, const qint32 y) const;
 
-    void updateExtent(qint32 col, qint32 row);
     void recalculateExtent();
 
     quint8* duplicatePixel(qint32 num, const quint8 *pixel);