Status of on-disk hash tables

2011-02-09
2013-04-25
1 2 > >> (Page 1 of 2)
  • Daniel Godás
    Daniel Godás
    2011-02-09

    Hi,

    I am working on a project for which I need an on-disk hash table to store data in the range of a terabyte. I read on the web site that on-disk hash tables are work in progress and I wondered if there is anything currently usable. I wouldn't mind testing experimental code and contributing to stabilize it. Any pointers?

     
  • You come along just the right time. There is a branch supporting this functionality

    https://stxxl.svn.sourceforge.net/svnroot/stxxl/branches/unordered_map

    It has the new container type unordered_map (corresponding to the C++0x one).
    We would appreciate if you could try and test that code.  Feel free to fix potential bugs, we could give you SVN write access.  But be aware that we synchronize this branch with the trunk every once in a while.

    Johannes

     
  • Daniel Godás
    Daniel Godás
    2011-02-10

    I've just checked out the branch, I've got a quick question before I delve into the code. How does the hash table (and all other containers) handle smart pointers? If I store shared_ptr<my_class> instances in the hash table will they get destroyed and recreated every time they get sent to disk storage and retrieved? Of course if this is the case very odd things can happen but I can't think of an elegant way to avoid the problem.

    Dan

     
  • The shared_ptr will neither be constructed nor destructed, they will just be read/written byte by byte.
    Apart from that, they will be reassigned when the internal memory of a written block is reused.
    But I assume that the shared_ptrs are linked somehow, so what happens if a particular one is currently swapped out, but accessed, or resurrected all of a sudden?

    But please be aware that STXXL in principle does not support overloaded assignment/copy constructor, which argues again shared_ptr.
    http://algo2.iti.kit.edu/stxxl/trunk/FAQ.html

    As a conclusion, it is very unlikely that shared_ptr wil work.  However, you might be able to write a well-crafted variant or a proxy class that satisfies all needs.  Maybe this would have to be more explicit, i. e. no overloading of assignment operator, but methods like copy(), move() and/or duplicate().

    Johannes

     
  • Daniel Godás
    Daniel Godás
    2011-02-10

    The shared_ptr will decrease the refcount when it goes out of scope. There is no problem with the serialization part (writing it byte by byte) as it will store the refcount.

    The problem comes when the shared_ptr goes out of scope as it will decrease the refcount and destroy the object if it gets to 0. The sensible behaviour would be to keep a refcount of +1 as the shared_ptr it is now stored in the stxxl container but this looks very difficult to achieve (impossible?) as the refcount cant be maintained when the object is on disk.

    I have read through the documentation and saw that no references to internal memory can be kept in the stored elements. This rules out the possibility of storing shared pointers but it makes sense so I will give up the shared_ptr idea for now. In boost they have a serialization class that can handle shared pointers, this might be something to look into if they are ever going to be supported.

    Now I will try to compile and test the unordered_map and probably come back with more questions :)

    Dan

     
  • Well, in principle you can store pointers.  The referenced object must just stay in internal  memory and not move.  The paragraph in the doc means that there should not be a "heap" part of the object, e.g. something that is dynamically allocated in the constructor for the exclusive use of the object.  We might rephrase that…
    AFAICS, shared_ptr has a pointer to a reference counter that is shared by all shared_ptr pointing to the same object.
    This is where the actual problem is.  As said before, you would need some smart pointer that changes the reference count only if explicitly told so.  However, this ruins most of the virtues of shared_ptr.

    Johannes

    Johannes

     
  • Daniel Godás
    Daniel Godás
    2011-02-10

    I tried to run the tests for the hash_map and found that test_hash_map.pmstxxl.bin fails in parallel mode but not in single threaded mode. It is the first test I tried, there might be a similar problem with other tests. The problem is the following piece of code:

        std::cout << "Initial import…";
        assert(map.begin() == map.end());
        map.insert(values1.begin(), values1.end(), mem_to_sort);
        assert(map.begin() != map.end());
        assert(map.size() == n_values);   // <---- This assertion fails
        std::cout << "passed" << std::endl;

    When constructing the value vectors the function rand_pairs is used. I haven't checked it but it looks like either it uses the clock to seed itself or it is not fully thread-safe. I added the following traces and piped the output to a file:

        std::cout << "Initial import…";
        assert(map.begin() == map.end());
    std::cout << "\n1 -> " << n_values << " ?= " << values1.size() << "\n";
    for (std::vector<value_type>::iterator it = values1.begin(); it != values1.end(); it++) {
        std::cout << "(" << it->first << "," << it->second << ")\n";
    }
        map.insert(values1.begin(), values1.end(), mem_to_sort);
        assert(map.begin() != map.end());
    std::cout << "\n2 -> " << n_values << " ?= " << map.size() << "\n";
        assert(map.size() == n_values);

    Pipping the file through sort (cat output | sort | less) you will see there are many repeated values. All the duplicates get filtered in include/stxxl/bits/containers/hash_map/hash_map.h:1343 so the final size of the container is always less than expected. With the single threaded version the chance of getting a duplicate is way lower so the test passes almost every time (I never saw it fail). For this test I would suggest a deterministic algorithm to generate the keys-value pairs at least until the hash_map becomes stable.

    Do you have a preferred way to submit patches or should I just post messages like this one when I find something buggy?

    Dan

     
  • Should be fixed.  I also merged with trunk.

    So far, post patches here.

    Johannes

     
  • Daniel Godás
    Daniel Godás
    2011-02-12

    I have written a wrapper template so that all the containers can store shared pointers. The reference count is incremented when the pointer is wrapped and decremented when it is unwrapped. The wrapper class can generate a wrapped pointer object suitable for being stored or provide access to the internal pointer.

    I put the wrapper in a header file in include/stxxl/bits/utils/ and modified test_map as a proof of concept. I am looking forward to any comments or suggestions.

    Index: include/stxxl/bits/utils/shared_ptr.h

    -- include/stxxl/bits/utils/shared_ptr.h (revision 0)
    +++ include/stxxl/bits/utils/shared_ptr.h (revision 0)
    @@ -0,0 +1,109 @@
    +/***************************************************************************
    + *  include/stxxl/bits/utils/shared_ptr.h
    + *
    + *  Part of the STXXL. See http://stxxl.sourceforge.net
    + *
    + *  Copyright (C) 2011 Daniel Godas-Lopez <dgodas@gmail.com>
    + *
    + *  Distributed under the Boost Software License, Version 1.0.
    + *  (See accompanying file LICENSE_1_0.txt or copy at
    + *  http://www.boost.org/LICENSE_1_0.txt)
    + **************************************************************************/
    +
    +#ifndef STXXL_SHARED_PTR_H
    +#define STXXL_SHARED_PTR_H
    +
    +#include <stxxl/bits/namespace.h>
    +#include <stxxl/bits/common/mutex.h>
    +
    +
    +__STXXL_BEGIN_NAMESPACE
    +
    +
    +//! \brief Wrapper class to make the storage of shared pointers possible
    +
    +//! the template parameter is the pointer class to be stored
    +template<class P>
    +class shared_ptr_wrapper
    +{
    +public:
    +    //! \brief wrapper class containing a shared pointer
    +    class wrapped_shared_ptr
    +    {
    +    friend class shared_ptr_wrapper<P>;
    +
    +    private:
    +    mutable P ptr;
    +
    +        //! \brief create the wrapper and store the pointer with
    +        //the incremeneted refcount
    +        wrapped_shared_ptr(P ptr) : ptr(ptr)
    +        {
    +        }
    +       
    +        //! \brief return the shared pointer and release the
    +        //internal instance
    +        P unwrap() const
    +        {
    +            P p = ptr;
    +            ptr.reset();
    +            return p;
    +        }
    +
    + P get() const
    + {
    +     return ptr;
    + }
    +
    + /*
    + * on copy the reference count of ptr will be incremented and it will
    + * be decremented again on destruction, just as expected.
    + */
    +
    +    public:
    +        wrapped_shared_ptr()
    + {
    + }
    +    };
    +
    +private:
    +    wrapped_shared_ptr staging;
    +    mutex staging_mutex;
    +
    +public:
    +    shared_ptr_wrapper()
    +    {
    +    }
    +
    +    /*
    +     * if there is a wrapped pointer in the staging area when this gets
    +     * destroyed then the refcount will be decremented as usual
    +     */
    +
    +    const wrapped_shared_ptr& wrap(P ptr)
    +    {
    +        scoped_mutex_lock lock(staging_mutex);
    + return *(new(&staging) wrapped_shared_ptr(ptr));
    +    }
    +
    +    P unwrap(const wrapped_shared_ptr& w)
    +    {
    +        scoped_mutex_lock lock(staging_mutex);
    + P p = w.unwrap();
    +
    +        // clear up the staging area, we don't want this destroyed twice
    + new(&staging) wrapped_shared_ptr();
    +
    +        return p;
    +    }
    +
    +    P get(const wrapped_shared_ptr& w)
    +    {
    +    scoped_mutex_lock lock(staging_mutex);
    + return w.get();
    +    }
    +};
    +
    +__STXXL_END_NAMESPACE
    +
    +#endif // !STXXL_SHARED_PTR_H
    Index: containers/test_map.cpp
    ===================================================================
    -- containers/test_map.cpp (revision 2958)
    +++ containers/test_map.cpp (working copy)
    @@ -15,9 +15,21 @@
    #include <stxxl/map>
    #include <stxxl/stats>

    +#include <stxxl/bits/utils/shared_ptr.h>
    +#include <memory>
    +
    typedef unsigned int key_type;
    -typedef unsigned int data_type;

    +struct test{
    +    unsigned short a;
    +    unsigned long b;
    +    unsigned int c;
    +};
    +
    +typedef std::shared_ptr<struct test> test_ptr;
    +typedef stxxl::shared_ptr_wrapper<test_ptr> wrapper_t;
    +typedef wrapper_t::wrapped_shared_ptr data_type;
    +
    struct cmp : public std::less<key_type>
    {
         static key_type min_value()
    @@ -45,7 +57,8 @@

         STXXL_MSG("Block size " << BLOCK_SIZE / 1024 << " KiB");
         STXXL_MSG("Cache size " << (CACHE_SIZE * BLOCK_SIZE) / 1024 << " KiB");
    -    int max_mult = 256;
    +//    int max_mult = 256;
    +    int max_mult = 5;
         if (argc > 1)
             max_mult = atoi(argv);
         for (int mult = 1; mult < max_mult; mult *= 2)
    @@ -58,9 +71,18 @@
             //map_type  Map(CACHE_SIZE*BLOCK_SIZE/2,CACHE_SIZE*BLOCK_SIZE/2);
             map_type & Map = *DMap;

    +        wrapper_t wrapper;
    +
             for (unsigned i = 0; i < el; ++i)
             {
    -            Map_ = i + 1;
    +            test_ptr tmp_test = std::make_shared<struct test>();
    +            tmp_test->a = i + 1;
    +            for (unsigned j = 0; j < 3; j++)
    +                tmp_test->b = i + 2;
    +            tmp_test->c = i + 3;
    +
    +            const data_type& tmp_data = wrapper.wrap(tmp_test);
    +            Map = tmp_data;
             }
             stats_elapsed = stxxl::stats_data(*stxxl::stats::get_instance()) - stats_begin;
             double writes = double(stats_elapsed.get_writes()) / double(el);
    @@ -77,7 +99,13 @@
             {
                 key_type key = myrandom() % el;
                 map_type::const_iterator result = ConstMap.find(key);
    -            assert((*result).second == key + 1);
    +
    +            test_ptr tmp_test = wrapper.get((*result).second);
    +
    +            assert(tmp_test->a == key + 1);
    +            for (unsigned j = 0; j < 3; j++)
    +                assert(tmp_test->b == (key + 2));
    +            assert(tmp_test->c == (key + 3));
             }
             stats_elapsed = stxxl::stats_data(*stxxl::stats::get_instance()) - stats_begin;
             double reads = double(stats_elapsed.get_reads()) / logel;
    _

     
  • Daniel Godás
    Daniel Godás
    2011-02-12

    Sorry, I forgot something. You will need to compile the test with support for c++0x for the shared pointers to work. This is how I built them:

    COMPILER_GCC="g++-4.4.4 -std=c++0x" make tests_g++_pmode tests_g++

     
  • Thanks for the patch.  Chances are good that we will include it into STXXL, but I see some room for improvement:

    -Can we get away with the C++0x requirement?  Many GCC versions have shared_ptr in tr1/, or one could also use Boost.  Some ifdefs could improve compatibility.
    -Just adding "wrapper/wrapped" to the name is not significant enough for me.  What about "external_shared_ptr" and shared_ptr_externalizer?
    -The test program never uses unwrap.  Besides, you create an shared object for each external object, don't you?  Since these shared object will reside in and consume memory, this is not a good example for external memory, where many external objects should point to few internal shared objects.
    -Why do you need this member variable "staging" and the associated lock?  Couldn't you use a local char (or alloca) and placement-new it there? Could you maybe get rid of shared_ptr_wrapper altogether then, and just have wrapped_shared_ptr?
    -Please "codify" patches posted here.

    Johannes

     
  • Daniel Godás
    Daniel Godás
    2011-02-14

    -Can we get away with the C++0x requirement? Many GCC versions have shared_ptr in tr1/, or one could also use Boost. Some ifdefs could improve compatibility.

    Yes, I will add some ifdefs to build the test with different shared_ptr implementations. Anyway, this only matters for the test case as the wrapper class is independent from the shared pointer you use as long as it has a reset() method. If there is any other dependency of the wrapper with the shared_ptr implementation in use I would consider that a bug.

    -Just adding "wrapper/wrapped" to the name is not significant enough for me. What about "external_shared_ptr" and shared_ptr_externalizer?

    Agreed.

    -The test program never uses unwrap. Besides, you create an shared object for each external object, don't you? Since these shared object will reside in and consume memory, this is not a good example for external memory, where many external objects should point to few internal shared objects.

    Agreed. It was just a proof of concept, I will write a better test.

    -Why do you need this member variable "staging" and the associated lock? Couldn't you use a local char (or alloca) and placement-new it there? Could you maybe get rid of shared_ptr_wrapper altogether then, and just have wrapped_shared_ptr?

    Using a local char is problematic in architectures that need variables to be aligned (ARM comes to mind) as it doesn't take care of alignment. We could use an std::vector but I think the code is clearer with a variable of the right type. The overhead is just an empty constructor anyway. I liked the staging variable so that we can hold a reference to the pointer until it is unwrapped or the wrapper is reused.

    The only important idea about the code I sent is the use of placement-new to avoid decrementing the refcount simulating a reference held by the on-disk instance. The implementation details are subject to discussion, especially the lock.

    -Please "codify" patches posted here.

    Will do.

    I am currently chasing a problem with unordered_map that becomes evident when running the test_iterator test case. I get some warnings about a request refcount that should be 2 or higher but is found to be 1. This happens on destruction of the read and write queues for the underlying storage and I followed it down to the destruction of the qwqr thread. I will go on working on this but wanted to raise it in case someone else is further down the way.

     
  • Daniel Godás
    Daniel Godás
    2011-02-14

    I've got some info about the iterator bug I forgot to post in my last reply. The problem seems to be the prefetching code as there is no error when I comment out line 247 in iterator.h (reader_->enable_prefetching();).

    I believe the prefetcher should be stopped and all the queues flushed before object destruction but the code is relying on a defined destruction order for this. When the objects get destructed in an arbitrary order (the destruction order can't be controlled for stack objects) some request objects are destroyed before the worker has time to process them but before the worker is stopped. I could only reproduce this problem with the hash map so I don't believe there is anything wrong with the lower levels.

    I still haven't read through all the code so my logic might be completely wrong. Sorry if that's the case.

     
  • I believe the prefetcher should be stopped and all the queues flushed before object destruction but the code is relying on a defined destruction order for this.

    This is most likely the problem.  The prefetcher should wait for (and possibly cancel) all outstanding requests.

    Using a local char is problematic in architectures that need variables to be aligned (ARM comes to mind) as it doesn't take care of alignment. We could use an std::vector but I think the code is clearer with a variable of the right type. The overhead is just an empty constructor anyway. I liked the staging variable so that we can hold a reference to the pointer until it is unwrapped or the wrapper is reused.

    alloca should care about alignment, since it is a compiler intrinsic.  And using int or long long could also mitigate alignment issues.
    I'm not talking about the running time overhead of the constructor, my goal is to simplify the code.
    AFAICT the only purpose of shared_ptr_wrapper is to hold and to lock staging.  If we can get rid of staging, we can drop shared_ptr_wrapper and save half of the code, right?  And locking is indeed expensive.
    What is the point in holding the staging variable?  It is not related to the argument of unwrap anyway, right?
    So I do not understand the line

    new(&staging) wrapped_shared_ptr();
    

    Why is staging manipulated? the operation should be related to w somehow.
    And why is staging_mutex locked in get() although staging is not used at all?

    Johannes

     
  • Daniel Godás
    Daniel Godás
    2011-02-15

    Here goes the second version, these are the changes:
      - Got rid of the wrapper class
      - Only stack storage is used now (got rid of the staging area)
      - No mutex
      - No need to compile with -std=c++0x
      - Changed the names according to your suggestion

    It is important to note that the objects must be unwrapped manually. If we let the containers be destroyed when they go out of scope we will leak memory. This is the reason to have the last loop in the test.

    <code>
    Index: include/stxxl/bits/utils/external_shared_ptr.h
    ===================================================================
    -- include/stxxl/bits/utils/external_shared_ptr.h (revision 0)
    +++ include/stxxl/bits/utils/external_shared_ptr.h (revision 0)
    @@ -0,0 +1,54 @@
    +/***************************************************************************
    + *  include/stxxl/bits/utils/shared_ptr.h
    + *
    + *  Part of the STXXL. See http://stxxl.sourceforge.net
    + *
    + *  Copyright (C) 2011 Daniel Godas-Lopez <dgodas@gmail.com>
    + *
    + *  Distributed under the Boost Software License, Version 1.0.
    + *  (See accompanying file LICENSE_1_0.txt or copy at
    + *  http://www.boost.org/LICENSE_1_0.txt)
    + **************************************************************************/
    +
    +#ifndef STXXL_SHARED_PTR_H
    +#define STXXL_SHARED_PTR_H
    +
    +#include <stxxl/bits/namespace.h>
    +
    +
    +__STXXL_BEGIN_NAMESPACE
    +
    +
    +template<class P>
    +class external_shared_ptr
    +{
    +private:
    + P ptr;
    +
    +public:
    + external_shared_ptr()
    + {
    + }
    +
    + external_shared_ptr(P ptr) : ptr(ptr)
    + {
    + P tmp = ptr;
    + new(&tmp) P();
    + }
    +
    + P unwrap()
    + {
    + P tmp = ptr;
    + ptr.reset();
    + return tmp;
    + }
    +
    + P get() const
    + {
    + return ptr;
    + }
    +};
    +
    +__STXXL_END_NAMESPACE
    +
    +#endif // !STXXL_SHARED_PTR_H
    Index: containers/test_map.cpp
    ===================================================================
    -- containers/test_map.cpp (revision 2958)
    +++ containers/test_map.cpp (working copy)
    @@ -15,9 +15,22 @@
    #include <stxxl/map>
    #include <stxxl/stats>

    +#include <stxxl/bits/utils/external_shared_ptr.h>
    +#include <boost/make_shared.hpp>
    +#include <boost/shared_ptr.hpp>
    +
    typedef unsigned int key_type;
    -typedef unsigned int data_type;

    +class test{
    +public:
    +    unsigned short a;
    +    unsigned long b;
    +    unsigned int c;
    +};
    +
    +typedef boost::shared_ptr<class test> test_ptr;
    +typedef stxxl::external_shared_ptr<test_ptr> data_type;
    +
    struct cmp : public std::less<key_type>
    {
         static key_type min_value()
    @@ -60,7 +73,15 @@

             for (unsigned i = 0; i < el; ++i)
             {
    -            Map_ = i + 1;
    +            test_ptr test = boost::make_shared<class test>();
    +
    +            test->a = i + 1;
    +            for (unsigned j = 0; j < 3; j++)
    +                test->b = i + 2;
    +            test->c = i + 3;
    +
    +            data_type wrapped_test(test);
    +            Map = wrapped_test;
             }
             stats_elapsed = stxxl::stats_data(*stxxl::stats::get_instance()) - stats_begin;
             double writes = double(stats_elapsed.get_writes()) / double(el);
    @@ -71,13 +92,19 @@
             stats_begin = *stxxl::stats::get_instance();
             STXXL_MSG("Doing search");
             unsigned queries = el;
    -        const map_type & ConstMap = Map;
             stxxl::random_number32 myrandom;
             for (unsigned i = 0; i < queries; ++i)
             {
                 key_type key = myrandom() % el;
    -            map_type::const_iterator result = ConstMap.find(key);
    -            assert((*result).second == key + 1);
    +            map_type::iterator result = Map.find(key);
    +
    +            data_type data = (*result).second;
    +            test_ptr tmp = data.get();
    +
    +            assert(tmp->a == key + 1);
    +            for (unsigned j = 0; j < 3; j++)
    +                assert(tmp->b == (key + 2));
    +            assert(tmp->c == (key + 3));
             }
             stats_elapsed = stxxl::stats_data(*stxxl::stats::get_instance()) - stats_begin;
             double reads = double(stats_elapsed.get_reads()) / logel;
    @@ -85,6 +112,14 @@
             STXXL_MSG("reads/logel " << reads << " readsperq " << readsperq);
             STXXL_MSG(stats_elapsed);

    +        map_type::iterator it = Map.begin();
    +        while (it != Map.end()) {
    +            data_type data = (*it).second;
    +            Map.erase(it);
    +            data.unwrap();
    +            it = Map.begin();
    +        }
    +
             delete DMap;
         }

    </code>_

     
  • Daniel Godás
    Daniel Godás
    2011-02-15

    Argh! Wrong code tags, will get it right next time. Sorry…

     
  • The problem is that without

    , it eats [i]. So could you please post the patch again? The test_map fails for me as is.
    Johannes
    
     
  • Daniel Godás
    Daniel Godás
    2011-02-16

    It's failing randomly for me too. I will get back to you when I stabilize it, might take me some time as I won't be able to work on this until Monday next week.

     
  • Daniel Godás
    Daniel Godás
    2011-02-17

    This implementation passes the test in normal and parallel mode. Just need to find a portable way to do the alignment.

    Index: include/stxxl/bits/utils/external_shared_ptr.h
    ===================================================================
    --- include/stxxl/bits/utils/external_shared_ptr.h  (revision 0)
    +++ include/stxxl/bits/utils/external_shared_ptr.h  (revision 0)
    @@ -0,0 +1,68 @@
    +/***************************************************************************
    + *  include/stxxl/bits/utils/shared_ptr.h
    + *
    + *  Part of the STXXL. See http://stxxl.sourceforge.net
    + *
    + *  Copyright (C) 2011 Daniel Godas-Lopez <dgodas@gmail.com>
    + *
    + *  Distributed under the Boost Software License, Version 1.0.
    + *  (See accompanying file LICENSE_1_0.txt or copy at
    + *  http://www.boost.org/LICENSE_1_0.txt)
    + **************************************************************************/
    +
    +#ifndef STXXL_SHARED_PTR_H
    +#define STXXL_SHARED_PTR_H
    +
    +#include <stxxl/bits/namespace.h>
    +
    +
    +__STXXL_BEGIN_NAMESPACE
    +
    +
    +template<class P>
    +class external_shared_ptr
    +{
    +private:
    +    /*
    +     * We store the pointer like this so that the refcount doesn't
    +     * get incremented when the wrapper is copy-constructred or
    +     * decremented when the wrapper is destroyed.
    +     */
    +    char data[sizeof(P)] __attribute__((aligned(8)));
    +
    +public:
    +    external_shared_ptr()
    +    {
    +        /*
    +         * This constructor needs to be defined so that the [] operator
    +         * in maps and hash tables works. If unwrap() or get() are called
    +         * for an object constructed this way the behaviour is undefined.
    +         */
    +    }
    +
    +    external_shared_ptr(P ptr)
    +    {
    +        // Copy the pointer to internal storage and increment
    +        // the refcount (the destructor never gets called)
    +        new(data) P(ptr);
    +    }
    +
    +    void unwrap()
    +    {
    +        // Call the destructor to decrement the refcount. If this is
    +        // called more than once the results are undefined.
    +        P* p = reinterpret_cast<P*>((void*) data);
    +        p->~P();
    +    }
    +
    +    P get() const
    +    {
    +        // If this is called after unwrap() the behaviour is undefined
    +        P* p = reinterpret_cast<P*>((void*) data);
    +        return *p;
    +    }
    +};
    +
    +__STXXL_END_NAMESPACE
    +
    +#endif // !STXXL_SHARED_PTR_H
    Index: containers/test_map.cpp
    ===================================================================
    --- containers/test_map.cpp (revision 2958)
    +++ containers/test_map.cpp (working copy)
    @@ -15,9 +15,22 @@
     #include <stxxl/map>
     #include <stxxl/stats>
    
    +#include <stxxl/bits/utils/external_shared_ptr.h>
    +#include <boost/make_shared.hpp>
    +#include <boost/shared_ptr.hpp>
    +
     typedef unsigned int key_type;
    -typedef unsigned int data_type;
    
    +class test{
    +public:
    +    unsigned char a;
    +    unsigned long b[3];
    +    unsigned int c;
    +};
    +
    +typedef boost::shared_ptr<class test> test_ptr;
    +typedef stxxl::external_shared_ptr<test_ptr> data_type;
    +
     struct cmp : public std::less<key_type>
     {
         static key_type min_value()
    @@ -60,8 +73,17 @@
    
             for (unsigned i = 0; i < el; ++i)
             {
    -            Map[i] = i + 1;
    +            test_ptr test = boost::make_shared<class test>();
    +
    +            test->a = (i + 1) % 256;
    +            for (unsigned j = 0; j < 3; ++j)
    +                test->b[j] = i + 2;
    +            test->c = i + 3;
    +
    +            data_type data(test);
    +            Map[i] = data;
             }
    +
             stats_elapsed = stxxl::stats_data(*stxxl::stats::get_instance()) - stats_begin;
             double writes = double(stats_elapsed.get_writes()) / double(el);
             double logel = log(double(el)) / log(double(BLOCK_SIZE));
    @@ -71,13 +93,21 @@
             stats_begin = *stxxl::stats::get_instance();
             STXXL_MSG("Doing search");
             unsigned queries = el;
    -        const map_type & ConstMap = Map;
             stxxl::random_number32 myrandom;
             for (unsigned i = 0; i < queries; ++i)
             {
                 key_type key = myrandom() % el;
    -            map_type::const_iterator result = ConstMap.find(key);
    -            assert((*result).second == key + 1);
    +            map_type::iterator result = Map.find(key);
    +
    +            data_type data = (*result).second;
    +            test_ptr tmp = data.get();
    +
    +       volatile test xxx = *tmp;
    +
    +            assert(tmp->a == (key + 1) % 256);
    +            for (unsigned j = 0; j < 3; ++j)
    +                assert(tmp->b[j] == (key + 2));
    +            assert(tmp->c == (key + 3));
             }
             stats_elapsed = stxxl::stats_data(*stxxl::stats::get_instance()) - stats_begin;
             double reads = double(stats_elapsed.get_reads()) / logel;
    @@ -85,6 +115,13 @@
             STXXL_MSG("reads/logel " << reads << " readsperq " << readsperq);
             STXXL_MSG(stats_elapsed);
    
    +        while (Map.size() != 0) {
    +            map_type::iterator it = Map.begin();
    +            data_type data = (*it).second;
    +            Map.erase(it);
    +            data.unwrap();
    +        }
    +
             delete DMap;
         }
    
     
  • Daniel Godás
    Daniel Godás
    2011-02-18

    Just a comment. I put the following line in the test so that the compiler didn't optimize out the value of tmp. I used it when debugging and forgot to remove it.

    volatile test xxx = *tmp;
    

    When we are happy with the code how would you like to test it? Should I add a test case for each container or create a new file with all the tests for the wrapper?

     
  • The code looks much better now.

    Minor things:
    -Could you please try __attribute__((aligned(sizeof(P)))), "8" is very hardcoded?  However, there is an interesting discussion on a related topic that makes me less worried about the alignment issues:
    http://stackoverflow.com/questions/4009463/alignment-of-char-arrays
    Does it really fail for you without the alignment specification?
    -I like the many comments around. Could you also comment on the fact that P must be a shared_ptr (or what else would also fit?)

    You do not have to write a test for each combination of container and the wrapper, but probably a test with vector, the most canonical data type, would be good in addition.  You can put it into the same file, just rename it to test_external_shared_ptr.

    Johannes

     
  • Daniel Godás
    Daniel Godás
    2011-02-21

    I've added another big comment at the top about the alignment and removed the hardcoded attribute. I also added a comment explaining what kind of objects can be wrapped and put tests with the vector and map containers into a separate file. This passed the tests in normal and parallel mode. Unless there is something you'd like me to change I would leave it like this and move on to that bug with the unordered map iterators.

    Index: include/stxxl/bits/utils/external_shared_ptr.h
    ===================================================================
    --- include/stxxl/bits/utils/external_shared_ptr.h  (revision 0)
    +++ include/stxxl/bits/utils/external_shared_ptr.h  (revision 0)
    @@ -0,0 +1,110 @@
    +/***************************************************************************
    + *  include/stxxl/bits/utils/external_shared_ptr.h
    + *
    + *  Part of the STXXL. See http://stxxl.sourceforge.net
    + *
    + *  Copyright (C) 2011 Daniel Godas-Lopez <dgodas@gmail.com>
    + *
    + *  Distributed under the Boost Software License, Version 1.0.
    + *  (See accompanying file LICENSE_1_0.txt or copy at
    + *  http://www.boost.org/LICENSE_1_0.txt)
    + **************************************************************************/
    +
    +#ifndef STXXL_EXTERNAL_SHARED_PTR_H
    +#define STXXL_EXTERNAL_SHARED_PTR_H
    +
    +#include <stxxl/bits/namespace.h>
    +
    +
    +__STXXL_BEGIN_NAMESPACE
    +
    +
    +/*
    + * This class takes a shared pointer, increments it's reference count and
    + * wraps it in a way that the resulting object can be copied, dumped to disk,
    + * and destroyed without affecting the refcount. When the object is retrieved
    + * from disk and recreated on internal memory it will still hold a reference
    + * to the same memory block and can be used right away by calling the "get"
    + * method or unwrapped with the "unwrap" method to decrement the refcount.
    + *
    + * In the context of this template a shared pointer is an object of a class P
    + * that fulfills the following requirements:
    + *
    + *   - Can be copy-constructed
    + *   - Have an assignment operator (so that the get method can be used)
    + *   - Contains a pointer to a reference count stored outside the class
    + *   - Increments the reference count on copy-construction
    + *   - Decrements the reference count on destruction
    + *
    + * Both the Boost and c++0x implementations of shared_ptr fulfill these
    + * requirements. At the moment of writing I [Dan] am not aware of any
    + * implementations of shared pointers that can't be used with this wrapper.
    + */
    +template<class P>
    +class external_shared_ptr
    +{
    +private:
    +    /*
    +     * We store the pointer like this so that the refcount doesn't
    +     * get incremented when the wrapper is copy-constructred or
    +     * decremented when the wrapper is destroyed.
    +     *
    +     * The whole external_shared_ptr object will be aligned by the compiler
    +     * to a multiple of it's size. The size of the object is sizeof(P) as the
    +     * buffer is it's only member. The buffer is placed in the class at offset
    +     * 0 so the alignment of the stored P should be alright without any
    +     * additional hints.
    +     */
    +    char data[sizeof(P)];
    +    
    +
    +public:
    +    external_shared_ptr()
    +    {
    +        /*
    +         * This constructor needs to be defined so that the [] operator
    +         * in maps and hash tables works. If unwrap() or get() are called
    +         * for an object constructed this way the behaviour is undefined.
    +         */
    +    }
    +
    +    external_shared_ptr(P ptr)
    +    {
    +        /*
    +         * Copy the pointer to internal storage and increment
    +         * the refcount (the destructor never gets called).
    +         */
    +        new(data) P(ptr);
    +    }
    +
    +    void unwrap()
    +    {
    +        /*
    +         * Call the destructor to decrement the refcount. If this is
    +         * called more than once the results are undefined.
    +         */
    +        P* p = reinterpret_cast<P*>((void*) data);
    +        p->~P();
    +    }
    +
    +    P get() const
    +    {
    +        /*
    +         * If this is called after unwrap() the behaviour is undefined
    +         */
    +        P* p = reinterpret_cast<P*>((void*) data);
    +        return *p;
    +    }
    +
    +    bool operator == (const external_shared_ptr& x) const
    +    {
    +        P* p1 = reinterpret_cast<P*>((void*) data);
    +        P* p2 = reinterpret_cast<P*>((void*) x.data);
    +
    +        return *p1 == *p2;
    +    }
    +};
    +
    +__STXXL_END_NAMESPACE
    +
    +#endif // !STXXL_EXTERNAL_SHARED_PTR_H
    Index: misc/run-all-tests
    ===================================================================
    --- misc/run-all-tests  (revision 2975)
    +++ misc/run-all-tests  (working copy)
    @@ -162,6 +162,7 @@
     run containers/test_vector_sizes "$STXXL_TMPDIR/out" syscall
     run containers/test_vector_sizes "$STXXL_TMPDIR/out" mmap
     run containers/test_vector_sizes "$STXXL_TMPDIR/out" boostfd
    +run containeds/test_external_shared_ptr
     run containers/benchmark_naive_matrix
     run containers/test_map 32
     run containers/test_map_random 2000
    Index: containers/test_external_shared_ptr.cpp
    ===================================================================
    --- containers/test_external_shared_ptr.cpp (revision 0)
    +++ containers/test_external_shared_ptr.cpp (revision 0)
    @@ -0,0 +1,298 @@
    +/***************************************************************************
    + *  containers/test_external_shared_ptr.cpp
    + *
    + *  Part of the STXXL. See http://stxxl.sourceforge.net
    + *
    + *  Copyright (C) 2011 Daniel Godas-Lopez <dgodas@gmail.com>
    + *
    + *  This file has been derived from the following tests written
    + *  by Roman Dementiev:
    + *     - test_vector.cpp
    + *     - test_map.cpp
    + *
    + *  Distributed under the Boost Software License, Version 1.0.
    + *  (See accompanying file LICENSE_1_0.txt or copy at
    + *  http://www.boost.org/LICENSE_1_0.txt)
    + **************************************************************************/
    +
    +#include <iostream>
    +#include <algorithm>
    +#include <cmath>
    +#include <stxxl/vector>
    +#include <stxxl/scan>
    +#include <stxxl/map>
    +#include <stxxl/stats>
    +
    +#include <stxxl/bits/utils/external_shared_ptr.h>
    +#include <boost/make_shared.hpp>
    +#include <boost/shared_ptr.hpp>
    +
    +struct actual_element  // 24 bytes, not a power of 2 intentionally
    +{
    +    stxxl::int64 key;
    +    stxxl::int64 load0;
    +    stxxl::int64 load1;
    +
    +    actual_element & operator = (stxxl::int64 i)
    +    {
    +        key = i;
    +        load0 = i + 42;
    +        load1 = i ^ 42;
    +        return *this;
    +    }
    +
    +    bool operator == (const actual_element & e2) const
    +    {
    +        return key == e2.key && load0 == e2.load0 && load1 == e2.load1;
    +    }
    +};
    +
    +typedef boost::shared_ptr<actual_element> actual_element_ptr;
    +typedef stxxl::external_shared_ptr<actual_element_ptr> element;
    +
    +struct counter
    +{
    +    int value;
    +    counter(int v) : value(v) { }
    +    int operator () ()
    +    {
    +        int old_val = value;
    +        value++;
    +        return old_val;
    +    }
    +};
    +
    +template <class my_vec_type>
    +void test_const_iterator(const my_vec_type & x)
    +{
    +    typename my_vec_type::const_iterator i = x.begin();
    +    i = x.end() - 1;
    +    i.block_externally_updated();
    +    i.flush();
    +    i++;
    +    ++i;
    +    --i;
    +    i--;
    +    *i;
    +}
    +
    +
    +void test_vector()
    +{
    +    try
    +    {
    +        // use non-randomized striping to avoid side effects on random generator
    +        typedef stxxl::VECTOR_GENERATOR<element, 2, 2, (2 * 1024 * 1024), stxxl::striping>::result vector_type;
    +        vector_type v(64 * 1024 * 1024 / sizeof(element));
    +
    +        // test assignment const_iterator = iterator
    +        vector_type::const_iterator c_it = v.begin();
    +        STXXL_UNUSED(c_it);
    +
    +        unsigned int big_size = 1024 * 1024 * 2 * 16 * 16;
    +        typedef stxxl::vector<double> vec_big;
    +        vec_big my_vec(big_size);
    +
    +        vec_big::iterator big_it = my_vec.begin();
    +        big_it += 6;
    +
    +        test_const_iterator(v);
    +
    +        stxxl::random_number32 rnd;
    +        int offset = rnd();
    +
    +        STXXL_MSG("write " << v.size() << " elements");
    +
    +        stxxl::ran32State = 0xdeadbeef;
    +        vector_type::size_type i;
    +
    +        // fill the vector with increasing sequence of integer numbers
    +        for (i = 0; i < v.size(); ++i)
    +        {
    +            actual_element_ptr aep(boost::make_shared<actual_element>());
    +            aep->key = i + offset;
    +            element e(aep);
    +
    +            v[i] = e;
    +
    +            assert(v[i].get()->key == stxxl::int64(i + offset));
    +        }
    +
    +        // fill the vector with random numbers
    +        for (i = 0; i < v.size(); ++i)
    +        {
    +            actual_element_ptr aep(boost::make_shared<actual_element>());
    +            aep->key = rnd();
    +            element e(aep);
    +
    +            v[i] = e;
    +
    +            assert(v[i].get()->key == aep->key);
    +        }
    +        v.flush();
    +
    +        STXXL_MSG("seq read of " << v.size() << " elements");
    +
    +        stxxl::ran32State = 0xdeadbeef;
    +
    +        // testing swap
    +        vector_type a;
    +        std::swap(v, a);
    +        std::swap(v, a);
    +
    +        for (i = 0; i < v.size(); i++)
    +            assert(v[i].get()->key == rnd());
    +
    +        // check again
    +        STXXL_MSG("clear");
    +
    +        v.clear();
    +
    +        stxxl::ran32State = 0xdeadbeef + 10;
    +
    +        v.resize(64 * 1024 * 1024 / sizeof(element));
    +
    +        STXXL_MSG("write " << v.size() << " elements");
    +        for (i = 0; i < v.size(); ++i)
    +        {
    +            actual_element_ptr aep(boost::make_shared<actual_element>());
    +            aep->key = rnd();
    +            element e(aep);
    +
    +            v[i] = e;
    +
    +            assert(v[i].get()->key == aep->key);
    +        }
    +
    +        stxxl::ran32State = 0xdeadbeef + 10;
    +
    +        STXXL_MSG("seq read of " << v.size() << " elements");
    +
    +        for (i = 0; i < v.size(); i++)
    +            assert(v[i].get()->key == rnd());
    +
    +        STXXL_MSG("copy vector of " << v.size() << " elements");
    +
    +        vector_type v_copy0(v);
    +        assert(v == v_copy0);
    +
    +        vector_type v_copy1;
    +        v_copy1 = v;
    +        assert(v == v_copy1);
    +    }
    +    catch (const std::exception & ex)
    +    {
    +        STXXL_MSG("Caught exception: " << ex.what());
    +    }
    +    catch (...)
    +    {
    +        STXXL_MSG("Caught unknown exception.");
    +    }
    +}
    +
    +typedef unsigned int key_type;
    +
    +struct test_data {
    +    unsigned char a;
    +    unsigned long b[3];
    +    unsigned int c;
    +};
    +
    +typedef boost::shared_ptr<test_data> test_data_ptr;
    +typedef stxxl::external_shared_ptr<test_data_ptr> data_type;
    +
    +struct cmp : public std::less<key_type>
    +{
    +    static key_type min_value()
    +    {
    +        return (std::numeric_limits<key_type>::min)();
    +    }
    +    static key_type max_value()
    +    {
    +        return (std::numeric_limits<key_type>::max)();
    +    }
    +};
    +
    +#define BLOCK_SIZE (32 * 1024)
    +#define CACHE_SIZE (2 * 1024 * 1024 / BLOCK_SIZE)
    +
    +#define CACHE_ELEMENTS (BLOCK_SIZE * CACHE_SIZE / (sizeof(key_type) + sizeof(data_type)))
    +
    +typedef stxxl::map<key_type, data_type, cmp, BLOCK_SIZE, BLOCK_SIZE> map_type;
    +
    +void test_map()
    +{
    +    stxxl::stats_data stats_begin(*stxxl::stats::get_instance());
    +    stxxl::stats_data stats_elapsed;
    +    STXXL_MSG(stats_begin);
    +
    +    STXXL_MSG("Block size " << BLOCK_SIZE / 1024 << " KiB");
    +    STXXL_MSG("Cache size " << (CACHE_SIZE * BLOCK_SIZE) / 1024 << " KiB");
    +    int max_mult = 256;
    +    for (int mult = 1; mult < max_mult; mult *= 2)
    +    {
    +        stats_begin = *stxxl::stats::get_instance();
    +        const unsigned el = mult * (CACHE_ELEMENTS / 8);
    +        STXXL_MSG("Elements to insert " << el << " volume =" <<
    +                  (el * (sizeof(key_type) + sizeof(data_type))) / 1024 << " KiB");
    +        map_type * DMap = new map_type(CACHE_SIZE * BLOCK_SIZE / 2, CACHE_SIZE * BLOCK_SIZE / 2);
    +        map_type & Map = *DMap;
    +
    +        for (unsigned i = 0; i < el; ++i)
    +        {
    +            test_data_ptr test = boost::make_shared<test_data>();
    +
    +            test->a = (i + 1) % 256;
    +            for (unsigned j = 0; j < 3; j++)
    +                test->b[j] = i + 2;
    +            test->c = i + 3;
    +
    +            data_type data(test);
    +            Map[i] = data;
    +        }
    +        stats_elapsed = stxxl::stats_data(*stxxl::stats::get_instance()) - stats_begin;
    +        double writes = double(stats_elapsed.get_writes()) / double(el);
    +        double logel = log(double(el)) / log(double(BLOCK_SIZE));
    +        STXXL_MSG("Logs: writes " << writes << " logel " << logel << " writes/logel " << (writes / logel));
    +        STXXL_MSG(stats_elapsed);
    +
    +        stats_begin = *stxxl::stats::get_instance();
    +        STXXL_MSG("Doing search");
    +        unsigned queries = el;
    +        stxxl::random_number32 myrandom;
    +        for (unsigned i = 0; i < queries; ++i)
    +        {
    +            key_type key = myrandom() % el;
    +            map_type::iterator result = Map.find(key);
    +
    +            data_type data = (*result).second;
    +            test_data_ptr tmp = data.get();
    +
    +            assert(tmp->a == (key + 1) % 256);
    +            for (unsigned j = 0; j < 3; ++j)
    +                assert(tmp->b[j] == (key + 2));
    +            assert(tmp->c == (key + 3));
    +        }
    +        stats_elapsed = stxxl::stats_data(*stxxl::stats::get_instance()) - stats_begin;
    +        double reads = double(stats_elapsed.get_reads()) / logel;
    +        double readsperq = double(stats_elapsed.get_reads()) / queries;
    +        STXXL_MSG("reads/logel " << reads << " readsperq " << readsperq);
    +        STXXL_MSG(stats_elapsed);
    +
    +        while (Map.size() != 0) {
    +            map_type::iterator it = Map.begin();
    +            data_type data = (*it).second;
    +            Map.erase(it);
    +            data.unwrap();
    +        }
    +
    +        delete DMap;
    +    }
    +}
    +
    +int main()
    +{
    +        test_vector();
    +        test_map();
    +        return 0;
    +}
    Index: containers/Makefile
    ===================================================================
    --- containers/Makefile (revision 2975)
    +++ containers/Makefile (working copy)
    @@ -127,7 +127,12 @@
        $(COMPILER) $(STXXL_COMPILER_OPTIONS) -c test_vector_sizes.cpp
        $(LINKER) test_vector_sizes.$(OBJEXT) $(OUT)test_vector_sizes.$(EXEEXT) $(STXXL_LINKER_OPTIONS)
    
    +test_external_shared_ptr: test_external_shared_ptr.$(EXEEXT)
    +test_external_shared_ptr.$(EXEEXT): test_external_shared_ptr.cpp $(DEPENDENCIES)
    +   $(COMPILER) $(STXXL_COMPILER_OPTIONS) -c test_external_shared_ptr.cpp
    +   $(LINKER)  test_external_shared_ptr.$(OBJEXT) $(OUT)test_external_shared_ptr.$(EXEEXT) $(STXXL_LINKER_OPTIONS)
    
    +
     clean:
        $(RM) $(CLEAN_TARGETS)
        cd btree
    Index: containers/Makefile.common
    ===================================================================
    --- containers/Makefile.common  (revision 2975)
    +++ containers/Makefile.common  (working copy)
    @@ -1,4 +1,4 @@
    -TESTS           = test_vector test_vector_export test_stack test_migr_stack test_many_stacks test_pqueue test_queue test_ext_merger test_ext_merger2 bench_pqueue copy_file test_deque test_iterators monotonic_pq pq_benchmark stack_benchmark write_vector write_vector2 benchmark_naive_matrix test_vector_sizes
    +TESTS           = test_vector test_vector_export test_stack test_migr_stack test_many_stacks test_pqueue test_queue test_ext_merger test_ext_merger2 bench_pqueue copy_file test_deque test_iterators monotonic_pq pq_benchmark stack_benchmark write_vector write_vector2 benchmark_naive_matrix test_vector_sizes test_external_shared_ptr
     TESTS_MAP       = test_map test_map_random
     TESTS_BDB       = berkeley_db_benchmark
     TESTS_LEDASM        = leda_sm_pq_benchmark leda_sm_stack_benchmark
    
     
  • I've added another big comment at the top about the alignment and removed the hardcoded attribute. I also added a comment explaining what kind of objects can be wrapped and put tests with the vector and map containers into a separate file. This passed the tests in normal and parallel mode. Unless there is something you'd like me to change I would leave it like this and move on to that bug with the unordered map iterators.

    Great.  I have added applied the patch to the unordered_map branch.  Let's see what the buildbot says about compatibility.
    But please go ahead with the iterator problem.

    Johannes

     
  • The vector test is a giant memory leak - the shared pointers get lost and the element they refereed to remains in memory.

    Andreas

     
  • Daniel Godás
    Daniel Godás
    2011-02-22

    Hehe yep, forgot to include the clean up loop as in the map test. I will send a patch for it tomorrow.

     
1 2 > >> (Page 1 of 2)