c++ - Alternative for std::set without memory reallocation? -

-

in application generate lot of subproblems exhaustively , solve them using "std::set" operations. need "insert" , "find" elements , "iterate" on sorted list.

the problem each of millions of subproblems "std::set" implementation allocates new memory each time insert element in set makes whole application slow:

{   // allocate non-value node     _nodeptr _pnode = this->_getal().allocate(1); // <- bottleneck of program

is there stl-structure allows me to above operations in "o(log(n))" while not reallocating memory?

using custom allocator seems way reduce amount of time spent building , releasing std::set<...>. below complete demo of simple allocator program profiling resulting times.

#include <algorithm> #include <chrono> #include <cstdlib> #include <iostream> #include <iterator> #include <memory> #include <set> #include <vector>  // ----------------------------------------------------------------------------  template <typename t, std::size_t pool_size = 1024> class pool_allocator { private:     std::vector<t*> d_pools;     t*              d_next;     t*              d_end; public:     template <typename o>     struct rebind {         typedef pool_allocator<o, pool_size> other;     };     pool_allocator(): d_next(), d_end() {}     ~pool_allocator() {         std::for_each(this->d_pools.rbegin(), this->d_pools.rend(),                       [](t* memory){ operator delete(memory); });     }     typedef t value_type;     t*   allocate(std::size_t n) {         if (std::size_t(this->d_end - this->d_next) < n) {             if (pool_size < n) {                 // custom allocation bigger number of objects                 this->d_pools.push_back(static_cast<t*>(operator new(sizeof(t) * n)));                 return this->d_pools.back();             }             this->d_pools.push_back(static_cast<t*>(operator new(sizeof(t) * pool_size)));             this->d_next = this->d_pools.back();             this->d_end  = this->d_next + pool_size;         }         t* rc(this->d_next);         this->d_next += n;         return rc;     }     void deallocate(t*, std::size_t) {         // try recycle buffers     } };  // ----------------------------------------------------------------------------  template <typename allocator> void time(char const* name, std::vector<int> const& random) {     std::cout << "running " << name << std::flush;     using namespace std::chrono;     high_resolution_clock::time_point start(high_resolution_clock::now());      std::size_t size(0);     {         std::set<int, std::less<int>, allocator> values;         (int value: random) {             values.insert(value);         }         size = values.size();     }      high_resolution_clock::time_point end(high_resolution_clock::now());     std::cout << ": size=" << size << " time="               << duration_cast<milliseconds>(end - start).count() << "ms\n"; }  // ----------------------------------------------------------------------------  int main() {     std::cout << "preparing..." << std::flush;     std::size_t count(10000000);     std::vector<int> random;     random.reserve(count);     std::generate_n(std::back_inserter(random), count, [](){ return std::rand(); });     std::cout << "done\n";      time<std::allocator<int>>("default allocator      ", random);     time<pool_allocator<int, 32>>("custom allocator (32)  ", random);     time<pool_allocator<int, 256>>("custom allocator (256) ", random);     time<pool_allocator<int, 1024>>("custom allocator (1024)", random);     time<pool_allocator<int, 2048>>("custom allocator (2048)", random);     time<pool_allocator<int, 4096>>("custom allocator (4096)", random);     time<std::allocator<int>>("default allocator      ", random); }  // results clang/libc++: // preparing...done // running default allocator      : size=10000000 time=13927ms // running custom allocator (32)  : size=10000000 time=9260ms // running custom allocator (256) : size=10000000 time=9511ms // running custom allocator (1024): size=10000000 time=9172ms // running custom allocator (2048): size=10000000 time=9153ms // running custom allocator (4096): size=10000000 time=9599ms // running default allocator      : size=10000000 time=13730ms  // results gcc/libstdc++: // preparing...done // running default allocator      : size=10000000 time=15814ms // running custom allocator (32)  : size=10000000 time=10868ms // running custom allocator (256) : size=10000000 time=10229ms // running custom allocator (1024): size=10000000 time=10556ms // running custom allocator (2048): size=10000000 time=10392ms // running custom allocator (4096): size=10000000 time=10664ms // running default allocator      : size=10000000 time=17941ms

Comments

Post a Comment

Popular posts from this blog

C# random value from dictionary and tuple -

-
i have following code, , need random item contains string "region_1" dictionary. public static dictionary<int, tuple<string, int, currencytype>> itemarray = new dictionary<int, tuple<string, int, currencytype>>() { { 0xb3e, new tuple<string, int, currencytype>("region_1", 1500, currencytype.fame) } }; public static int generateitemid(string shopid) { var generateditem = itemarray.elementat(new random().next(0, itemarray.count)).key; } how select this? it's not possible efficiently... first create static random @ class level... prevent non-random behaviour if run query on short period of time... (it's seeded discrete clock) static random rnd = new random(); then: var item = itemarray.values .where(t => t.item1 == shopid) .orderby(_ => rnd.next()) .firstordefault()
Read more

cgi - How do I interpret URLs without extension as files rather than missing directories in nginx? -

-
so i'm trying install zoneminder , have run under nginx, has few compiled files need run using fast-cgi. these files lack extension. if file has extension, there no issue , nginx interprets file , return 404 if can't find it. if has no extension, assume it's directory , return 404 when can't find sort of index page. here have now: # security camera domain. server { listen 888; server_name mydomain.com; root /srv/http/zm; # enable php support. include php.conf; location / { index index.html index.htm index.php; } # enable cgi support. location ~ ^/cgi-bin/(.+)$ { alias /srv/cgi-bin/zm/; fastcgi_pass unix:/run/fcgiwrap.sock; fastcgi_param script_filename $document_root/$1; include fastcgi.conf; } } the idea is, under cgi-bin directory goes through fastcgi pipe. any idea on howi can fix this? upon closer inspection, realized zoneminder has 2 cgi sc...
Read more

.htaccess - htaccess convert request to clean url and add slash at the end of the url -

-
ok , searched more 4 days , more 20 posts here in stach or in websites without kind of success first here htaccess file rewriteengine on rewriterule ^([a-za-z0-9_]+)/?$ index.php?page=$1 [nc] rewriterule ^([a-za-z0-9_]+)\/([a-za-z0-9_]+)\/?$ index.php?page=$1&action=$2 [nc] i tried many codes 1 worked me can call request , works me www.example.com/pagename => www.example.com/index.php?page=pagename here questions , please provide me information "in detail" understand code well 1- how convert request automatically www.example.com/index.php?page=pagename www.example.com/pagename 2- if tried add slash @ end shows me page without images or styling mean www.example.com/pagename => works www.example.com/pagename/ => doesn't work that's :) for first part need 301 rule this: rewritecond %{the_request} /index\.php\?page=([^\s&]+) [nc] rewriterule ^ /%1? [r=301,l] for second part use absolute path in css, js, images files r...
Read more