Возможно ли, чтобы STL был установлен быстрее, чем STL, для предотвращения дублирования записей?

Question

Добрый день, в настоящее время мы используем STL multimap и STL для кэширования областей отображаемых файлов. Мы бы хотели, чтобы в нашем кеше были только уникальные записи. Нам интересно, есть ли способ, чтобы STL set и STL map были быстрее, чем STL multiset и STL multimap для предотвращения дублирования записей. Мы используем следующий фрагмент кода для предотвращения многократного отображения STL и дублирования записей в STL. Можно ли сделать это быстрее? Спасибо.

int distance(char* x, char* y,int error){ 
    if (x >= y && (x - y) <= error){ 
        return 0;
    }
    return (x - y);
};

class MinDist {
public:
    MinDist(){}

    MinDist(char* & p, const int & error){}

    bool operator() (char *  p1, char *  p2 )
    {
      return distance( p1, myPoint, myError) < distance( p2,  myPoint, myError); 
    }

public:
    static char* myPoint;
    static int myError;
};


std::multiset<Range> ranges_type; 
std::multimap<char *,Range, MinDist> mmultimap;


MinDist::myPoint = TmpPrevMapPtr;
MinDist::myError = MEM_BLOCK_SIZE;

std::pair<I,I> b = mmultimap.equal_range(TmpPrevMapPtr); 
for (I i=b.first; i != b.second; ++i){ 
     ranges_type.erase(i->second);
     numerased++;
}

typedef std::multimap<char*,Range,MinDist>::iterator J;
std::pair<J,J> pr = mmultimap.equal_range(TmpPrevMapPtr); 


erasecount = 0;
J iter = pr.first;
J enditer = pr.second;
for(  ; iter != enditer ; ){ 
    if ((*iter).first == TmpPrevMapPtr){
        mmultimap.erase(iter++); 
        erasecount++;
    }
    else{
        ++iter;
    }
}

MinDist::myPoint = 0; 

ranges_type.insert(RangeMultiSet::value_type(n, n + mappedlength,
                &adjustedptr[n],MapPtr,mappedlength));


mmultimap.insert(RangeMultiMap::value_type(MapPtr,
                   Range(n,n + mappedlength,
                      &adjustedptr[n],
                      MapPtr,mappedlength)));

Answer 1

Здесь есть много чего почитать, и оптимизация сложных типов контейнеров является сложной задачей. Я потратил немало времени, работая над подобными проблемами, поэтому постараюсь указать на некоторые вещи, которые мне помогли.

Во-первых, обычный способ сделать ваш код быстрее: не использовать двоичные деревья, когда векторы будут делать . Реализация Microsoft STL будет тратить около 14 байт (3 указателя + короткое int для красного / черного флага, которое я недавно проверял) на служебные расходы для каждого узла в вашей карте / наборе, а также служебную нагрузку malloc как минимум еще на 4 байта, прежде чем она обойдет. для хранения данных вашего узла. Хотя я не очень хорошо знаю специфику вашего домена, ввод-вывод с отображением памяти кажется мне областью, где, вероятно, существует сложное, но более быстрое векторное решение. Это потребовало бы, чтобы число блоков, которые вы отображаете одновременно, было небольшим - если ваша таблица поиска не превышает 6000 байтов, реализация отсортированного массива с memmove для вставки / стирания и двоичным_поиском для поиска, вероятно, будет быстрее в Режим выпуска (и в режиме отладки, к сожалению, он будет быстрее до нескольких мегабайт). Если элементы являются 4-байтовыми указателями, то 6000 байтов позволяют разместить до 1500 отображенных блоков.

Однако иногда вам просто нужно использовать деревья. Один случай - это сложные узлы (так что создание / уничтожение имеет важное значение) или довольно большое количество элементов (так что вставка массива O (N) становится медленнее, чем стоимость malloc для вставки дерева O (log n)). Что вы можете сделать здесь? Обратите внимание, что map / multimap и set / multiset или почти одинаковая скорость; мульти * версии имеют тенденцию быть немного медленнее, но только потому, что код для их обработки на несколько строк длиннее.

В любом случае, одна вещь, которая может очень помочь, - это выяснить, как сократить стоимость malloc, поскольку каждый узел будет вызывать malloc / free в какой-то момент. Обрезка, которая трудная - распределитель режима Release примерно эквивалентен примерно 50-200 арифметическим операциям, поэтому, хотя он и выполним, он требует определенных усилий. Однако у вас есть некоторая надежда - все распределения карт / наборов имеют одинаковый размер, поэтому пул памяти может работать очень хорошо. Google , вероятно, хороший способ начать; Есть много хороших статей на эту тему.

Наконец, есть профилировщик выборки с открытым исходным кодом, который я считаю очень полезным - он называется Very Sleepy и обычно просто работает в проектах Visual Studio. Если вы хотите точно ответить, быстрее ли в вашем случае map / multimap или set / multiset, на это я бы вам указал. Удачи!

Answer 2

Вот общая ситуация:

#include <cstddef>   // for size_t
#include <set>       // for std::set
#include <algorithm> // for std::swap
#include <ostream>   // for std::ostream

struct Range
{
  int start, end; // interpret as [start, end), so Range(n,n) is empty!

  Range(int s, int e) : start(s), end(e)
  {
    if (start > end) std::swap(start, end);
  }

  inline bool operator<(const Range & r) const
  {
    return (start < r.start) || (!(r.start > start) && end < r.end);
  }

  inline size_t size() const { return end - start; }
};

std::ostream & operator<<(std::ostream & o, const Range & r)
{
  return o << "[" << r.start << ", " << r.end << ")";
}

typedef std::set<Range> cache_t;

cache_t::const_iterator findRange(int pos, const cache_t & cache)
{
  cache_t::const_iterator it = cache.lower_bound(Range(pos, pos)),
                         end = cache.end();

  for ( ; it != end && it->start <= pos ; ++it) // 1
  {
    if (it->end > pos) return it;
  }

  return end;
}

inline bool inRange(int pos, const cache_t & cache)
{
  return findRange(pos, cache) != cache.end();
}

Теперь вы можете использовать findRange(pos, cache), чтобы узнать, покрыта ли данная позиция диапазоном в кэше.

Обратите внимание, чтоцикл в // 1 довольно эффективен, поскольку он начинается только с первого элемента, где pos может быть, и останавливается, когда pos больше не может находиться в диапазоне.Для непересекающихся диапазонов это будет охватывать не более одного диапазона!

Answer 3

class Range { 
    public:   
        explicit Range(int item = 0)
        : mLow(item), mHigh(item), mPtr(0), mMapPtr(0) { }

        Range(int low, int high, char* ptr = 0, char * mapptr = 0, int currMappedLength = 0)
        : mLow(low), mHigh(high), mPtr(ptr), mMapPtr(mapptr), mMappedLength(currMappedLength) { }

        Range(const Range& r)
        : mLow(r.mLow), mHigh(r.mHigh), mMapPtr(r.mMapPtr), mMappedLength(r.mMappedLength) { }

        bool operator<(const Range& rhs) const { return mHigh < rhs.mHigh; }

        int   low()       const { return mLow; }   
        int   high()      const { return mHigh; }
        char* getMapPtr() const { return mMapPtr; }
        int getMappedLength() const { return mMappedLength; }

     private:   
         int mLow;          // beginning of memory mapped file region
         int mHigh;         // end of memory mapped file region 
         char* mMapPtr;     // return value from MapViewOfFile
         int mMappedLength; // length of memory mapped region
};