aboutsummaryrefslogtreecommitdiff
path: root/src/util
diff options
context:
space:
mode:
authorLoic Blot <loic.blot@unix-experience.fr>2015-02-15 17:30:38 +0100
committerLoic Blot <loic.blot@unix-experience.fr>2015-02-16 11:27:44 +0100
commit7c8793cbea1ea83109b7d9d6974d3f6991efcec8 (patch)
tree3a1c54acd3ee11fd73e11e81e2b83f917488a379 /src/util
parented04e8e9e407f0dd57fa83a9732b3a3968cb80e0 (diff)
downloadminetest-7c8793cbea1ea83109b7d9d6974d3f6991efcec8.tar.gz
minetest-7c8793cbea1ea83109b7d9d6974d3f6991efcec8.tar.bz2
minetest-7c8793cbea1ea83109b7d9d6974d3f6991efcec8.zip
Performance Improvement: Use a cache which caches result for getFacePositions.
This greatly reduce the number of std::list generated by caching the result, which is always constant for each radius selected. In the callgrind map, you will see original: * 3.3M calls to std::list for 9700 calls to getFacePositions In the modified version, you will see: * 3.3K calls to std::list for 6900 call to getFacePositions Callgrind map is here: #2321 it's a huge performance improvement to l_find_node_near
Diffstat (limited to 'src/util')
-rw-r--r--src/util/numeric.cpp114
-rw-r--r--src/util/numeric.h17
2 files changed, 74 insertions, 57 deletions
diff --git a/src/util/numeric.cpp b/src/util/numeric.cpp
index 6173515ee..19f927134 100644
--- a/src/util/numeric.cpp
+++ b/src/util/numeric.cpp
@@ -20,79 +20,84 @@ with this program; if not, write to the Free Software Foundation, Inc.,
#include "numeric.h"
#include "mathconstants.h"
-#include "../log.h"
+#include "log.h"
#include "../constants.h" // BS, MAP_BLOCKSIZE
#include <string.h>
#include <iostream>
+std::map<u16, std::vector<v3s16> > FacePositionCache::m_cache;
// Calculate the borders of a "d-radius" cube
-void getFacePositions(std::list<v3s16> &list, u16 d)
+std::vector<v3s16> FacePositionCache::getFacePositions(u16 d)
{
- if(d == 0)
- {
- list.push_back(v3s16(0,0,0));
+ if (m_cache.find(d) != m_cache.end())
+ return m_cache[d];
+
+ generateFacePosition(d);
+ return m_cache[d];
+
+}
+
+void FacePositionCache::generateFacePosition(u16 d)
+{
+ m_cache[d] = std::vector<v3s16>();
+ if(d == 0) {
+ m_cache[d].push_back(v3s16(0,0,0));
return;
}
- if(d == 1)
- {
+ if(d == 1) {
/*
This is an optimized sequence of coordinates.
*/
- list.push_back(v3s16( 0, 1, 0)); // top
- list.push_back(v3s16( 0, 0, 1)); // back
- list.push_back(v3s16(-1, 0, 0)); // left
- list.push_back(v3s16( 1, 0, 0)); // right
- list.push_back(v3s16( 0, 0,-1)); // front
- list.push_back(v3s16( 0,-1, 0)); // bottom
+ m_cache[d].push_back(v3s16( 0, 1, 0)); // top
+ m_cache[d].push_back(v3s16( 0, 0, 1)); // back
+ m_cache[d].push_back(v3s16(-1, 0, 0)); // left
+ m_cache[d].push_back(v3s16( 1, 0, 0)); // right
+ m_cache[d].push_back(v3s16( 0, 0,-1)); // front
+ m_cache[d].push_back(v3s16( 0,-1, 0)); // bottom
// 6
- list.push_back(v3s16(-1, 0, 1)); // back left
- list.push_back(v3s16( 1, 0, 1)); // back right
- list.push_back(v3s16(-1, 0,-1)); // front left
- list.push_back(v3s16( 1, 0,-1)); // front right
- list.push_back(v3s16(-1,-1, 0)); // bottom left
- list.push_back(v3s16( 1,-1, 0)); // bottom right
- list.push_back(v3s16( 0,-1, 1)); // bottom back
- list.push_back(v3s16( 0,-1,-1)); // bottom front
- list.push_back(v3s16(-1, 1, 0)); // top left
- list.push_back(v3s16( 1, 1, 0)); // top right
- list.push_back(v3s16( 0, 1, 1)); // top back
- list.push_back(v3s16( 0, 1,-1)); // top front
+ m_cache[d].push_back(v3s16(-1, 0, 1)); // back left
+ m_cache[d].push_back(v3s16( 1, 0, 1)); // back right
+ m_cache[d].push_back(v3s16(-1, 0,-1)); // front left
+ m_cache[d].push_back(v3s16( 1, 0,-1)); // front right
+ m_cache[d].push_back(v3s16(-1,-1, 0)); // bottom left
+ m_cache[d].push_back(v3s16( 1,-1, 0)); // bottom right
+ m_cache[d].push_back(v3s16( 0,-1, 1)); // bottom back
+ m_cache[d].push_back(v3s16( 0,-1,-1)); // bottom front
+ m_cache[d].push_back(v3s16(-1, 1, 0)); // top left
+ m_cache[d].push_back(v3s16( 1, 1, 0)); // top right
+ m_cache[d].push_back(v3s16( 0, 1, 1)); // top back
+ m_cache[d].push_back(v3s16( 0, 1,-1)); // top front
// 18
- list.push_back(v3s16(-1, 1, 1)); // top back-left
- list.push_back(v3s16( 1, 1, 1)); // top back-right
- list.push_back(v3s16(-1, 1,-1)); // top front-left
- list.push_back(v3s16( 1, 1,-1)); // top front-right
- list.push_back(v3s16(-1,-1, 1)); // bottom back-left
- list.push_back(v3s16( 1,-1, 1)); // bottom back-right
- list.push_back(v3s16(-1,-1,-1)); // bottom front-left
- list.push_back(v3s16( 1,-1,-1)); // bottom front-right
+ m_cache[d].push_back(v3s16(-1, 1, 1)); // top back-left
+ m_cache[d].push_back(v3s16( 1, 1, 1)); // top back-right
+ m_cache[d].push_back(v3s16(-1, 1,-1)); // top front-left
+ m_cache[d].push_back(v3s16( 1, 1,-1)); // top front-right
+ m_cache[d].push_back(v3s16(-1,-1, 1)); // bottom back-left
+ m_cache[d].push_back(v3s16( 1,-1, 1)); // bottom back-right
+ m_cache[d].push_back(v3s16(-1,-1,-1)); // bottom front-left
+ m_cache[d].push_back(v3s16( 1,-1,-1)); // bottom front-right
// 26
return;
}
// Take blocks in all sides, starting from y=0 and going +-y
- for(s16 y=0; y<=d-1; y++)
- {
+ for(s16 y=0; y<=d-1; y++) {
// Left and right side, including borders
- for(s16 z=-d; z<=d; z++)
- {
- list.push_back(v3s16(d,y,z));
- list.push_back(v3s16(-d,y,z));
- if(y != 0)
- {
- list.push_back(v3s16(d,-y,z));
- list.push_back(v3s16(-d,-y,z));
+ for(s16 z=-d; z<=d; z++) {
+ m_cache[d].push_back(v3s16(d,y,z));
+ m_cache[d].push_back(v3s16(-d,y,z));
+ if(y != 0) {
+ m_cache[d].push_back(v3s16(d,-y,z));
+ m_cache[d].push_back(v3s16(-d,-y,z));
}
}
// Back and front side, excluding borders
- for(s16 x=-d+1; x<=d-1; x++)
- {
- list.push_back(v3s16(x,y,d));
- list.push_back(v3s16(x,y,-d));
- if(y != 0)
- {
- list.push_back(v3s16(x,-y,d));
- list.push_back(v3s16(x,-y,-d));
+ for(s16 x=-d+1; x<=d-1; x++) {
+ m_cache[d].push_back(v3s16(x,y,d));
+ m_cache[d].push_back(v3s16(x,y,-d));
+ if(y != 0) {
+ m_cache[d].push_back(v3s16(x,-y,d));
+ m_cache[d].push_back(v3s16(x,-y,-d));
}
}
}
@@ -100,10 +105,9 @@ void getFacePositions(std::list<v3s16> &list, u16 d)
// Take the bottom and top face with borders
// -d<x<d, y=+-d, -d<z<d
for(s16 x=-d; x<=d; x++)
- for(s16 z=-d; z<=d; z++)
- {
- list.push_back(v3s16(x,-d,z));
- list.push_back(v3s16(x,d,z));
+ for(s16 z=-d; z<=d; z++) {
+ m_cache[d].push_back(v3s16(x,-d,z));
+ m_cache[d].push_back(v3s16(x,d,z));
}
}
diff --git a/src/util/numeric.h b/src/util/numeric.h
index db1eb003e..7fc3d2167 100644
--- a/src/util/numeric.h
+++ b/src/util/numeric.h
@@ -25,10 +25,23 @@ with this program; if not, write to the Free Software Foundation, Inc.,
#include "../irr_v3d.h"
#include "../irr_aabb3d.h"
#include <list>
+#include <map>
+#include <vector>
#include <algorithm>
-// Calculate the borders of a "d-radius" cube
-void getFacePositions(std::list<v3s16> &list, u16 d);
+
+/*
+ * This class permits to cache getFacePosition call results
+ * This reduces CPU usage and vector calls
+ */
+class FacePositionCache
+{
+public:
+ static std::vector<v3s16> getFacePositions(u16 d);
+private:
+ static void generateFacePosition(u16 d);
+ static std::map<u16, std::vector<v3s16> > m_cache;
+};
class IndentationRaiser
{