Thread: How Do I Make This Container Thread-Safe?

  1. #31
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Code:
    struct nontrivial {
      int *data;
      int m;
     
     // create a non-trivial default constructor to test
    // our container with (i.e. this class actually has consequenes
    // of living)
      nontrivial(void) {
        data = new int[256]; //?2
        mark(this);
      }
     
     // yeah, this is code that I should probably just throw away...
    // it was supposed to be a copy constructor but then I realized
    // I'm bad at programming. I rewrote some stuff today that
    // actually uses a real copy constructor.
    // My logic kind of was, hey, if the reference we're referencing lives longer
    // than the container, the reference in the container will always be valid. 
    // The only problem is if I call the destructor on this element from inside the container
    // which seems super likely to happen. So yes, this is code that's so bad it'd make me cry...
      nontrivial(const nontrivial &other) {
        data = other.data; //?2
        mark(this);
      }
     
     // again, code I should really delete...
    // it was supposed to clear the data if there was any
    // before the move so we don't have random chunks 
    // of memory just existing out there. It was a "my bad"
    // kind of thing.
      nontrivial(nontrivial &&other) {
        delete[] data; //?3
        data = other.data;
        other.data = nullptr;
        mark(this);
      }
     
     // again, safeguarding invalid deletes
    
      ~nontrivial(void) {
        unmark(this);
        if (data) //?$
          delete[] data; //?2
      }
    };
    Okay, now for a rundown...

    A main container allocates blocks of a type T. Insertions into the container are done using a free list. We can append blocks which append to the freelist so when we insert, we just pop off an element from the back and use that as our write address.

    But this code is mostly mine and it's mostly, well, wrong! I think it's when you unmark that you actually do the proper destructing but that shouldn't have to be in the destructor of a user-defined type.

    It's much better to just plain start over. Blank slate.

    Let's think about this.

    We need a container that can manage the responsibilities of owning objects. Ignoring the paging system for now (that's an implementation detail), we have a contigous allocation of elements, some of which may be invalid or non-existent. We allocate space for N objects but we do not necessarily have N objects. This means that it's silly to use new() in this sense because it'll automatically construct each element. Sometimes this is desired behavior like with std::vector::resize but we all know std::vector::reserve is kind of where it's at.

    We've acknowledged that the construction of elements is now decoupled from the allocation of memory. This means it's up to our container to destruct objects properly. I've decided that using a hash table is too computationally expensive. This means that all insertions into the container also include an insertion into the hash table and I don't feel like that's particuarly easier than storing the state of element and iterating the container, destructing the proper elements along the way.

    I'm going to keep working on this, though. I think I'm getting a little bit better at this. I'm beginning to understand what it is I'm actually doing so that's a good start.

    Because these may very well be my very last words to you, phantom, I'd like to say, thanks for always pushing me so hard. I hope my explanations were good enough. I didn't proofread as much as I should've so there's that but I think the gist is there.

  2. #32
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    I've actually been using this as a reference and it's really been helping : https://en.wikipedia.org/wiki/Rule_o...ple_in_C.2B.2B

    I've also been trying to read up more on move semantics too. Stuff is crazy. I think I can figure this stuff out, though.

  3. #33
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    We're constructing a new element using a copy of an old one.
    O_o

    You can't accomplish what you are trying to implement without understanding and controlling every aspect of the lifetime of objects, but you seem more interested in guessing which is why your code is still repeating some of the same abuses I referenced earlier in the thread, and I simply can not teach you to control the lifetime of objects while your head is buried in sand.

    A partial understanding of object lifetime does more harm than good, as you have shown, so I can't just give you two pages and a handful of examples this time. You are actually going to have to learn the foundations of the C++ language... or hope someone else gives you a pass.

    I hope my explanations were good enough.
    You explained how you wished the code would behave.

    I want an explanation for how the code actually behaves.

    *shrug*

    I'll talk to you if and when you can do that...

    [Edit]
    The STL has a multiset, you know.
    I wouldn't have thought of `std::multiset` for the example, but I agree (I think.) a `std::multiset` would have been more semantically correct.

    In fairness to me, the `mark`/`unmark` code is already repellent so the wrong container is only adding insult to injury.
    [/Edit]

    Soma
    “Salem Was Wrong!” -- Pedant Necromancer
    “Four isn't random!” -- Gibbering Mouther

  4. #34
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    If it makes you feel any better, my head isn't in the sand on purpose. I'm just bad at subtlety.

  5. #35
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    I'm also pretty stoked that your evaluation of my evaluation was so short! Maybe you just stopped on the first thing you saw...

    Here's the thing, I learn best by failing and by successful example. If you don't wanna help me, that's cool. But it's hard for me to get what you mean without seeing the full answer. Keep in mind, I only have my degree because of cramster so it is possible to learn even if someone does just give you the answer.

  6. #36
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Actually, I think I get what you mean now, phantom. It was the exception handling part. I did ignore that because I was like, "When I use this, my objects won't fail to construct because I know exactly what objects I'm going to put into this container."

    But from a generic, metaprogramming perspective, I can't ignore the possibility of a failed constructor.

    I found the isocpp site yesterday and this. I think it's a relevant read and pertinent to the situation.

    When I found this I was like, "So that's what he meant XD"

    Sorry. I'm a silly goose sometimes. But I think that's what you were alluding to, phantom.

  7. #37
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Alright, I've officially decided, I'm not going to give up on this!

    So, I tried to take some of your advice to heart, phantom. Forgive me if this code is still awful but and you'll like this (hopefully), it seems like my code is now constructor-excepting safe. I think. Basically, I defined a non-trivial constructor that throws. However, I did some more thorough testing and it looks like it's up to the programmer (the theoretical user of my code) to define their own RAII-style classes to prevent leaks when their constructors throw exceptions.

    So I guess if a user wants to define a constructor that throws, they need some sort of handling on their part. I'm still kind of unsure about this but I have my container's insert() routine throw the error that bubbles up from the bottom.

    Here's the code:
    container.hpp
    Code:
    #ifndef CONTAINER_HPP_ 
    #define CONTAINER_HPP_
    
    
    #include <vector>
    #include <exception>
    #include <iostream>
    #include <memory>
    #include <cstring>
    
    
    template<class T>
    class Element {
    private:
      char buffer_[sizeof(T)];
      bool alive_;
    
    
    public:
      Element(void) {
        memset(buffer_, 0, sizeof(T));
        alive_ = false;
      }
    
    
      template<class... Args>
      Element(Args&&... args) {
        std::cout << "Constructing a new Element by copy..." << std::endl;
        try {
          new(buffer_) T{args...};
          alive_ = true;
        }
        catch(std::exception &e) {
          memset(buffer_, 0, sizeof(T));
          alive_ = false;
          std::cout << e.what() << std::endl;
          throw e;
        }
      }
    
    
      T value(void) {
        T *data = reinterpret_cast<T*>(buffer_);
        return *data;
      }
    };
    
    
    template<class T>
    class Block {
    private:
      std::unique_ptr<Element<T>[]> elements_;
      size_t size_;
    
    
    public:
      Block(size_t num_elems) {
        std::cout << "Constructing a new Block..." << std::endl;
        try {
          size_ = num_elems;
          elements_ = std::unique_ptr<Element<T>[]>(new Element<T>[num_elems]);
        }
        catch(std::exception &e) {
          size_ = 0;
    
    
          std::cout << e.what() << std::endl;
        }
      }
    
    
      Block& operator[](size_t index) {
        if (index >= size_) throw std::out_of_range{"Invalid index"};
        return elements_[index];
      }
    
    
      size_t size(void) const {
        return size_;
      }
    
    
      Element<T>* data(void) {
        return elements_.get();
      }
    };
    
    
    template<class T>
    class Container {
    private:
      std::vector<std::unique_ptr<Block<T>>> blocks_;
      std::vector<Element<T>*> free_list_;
      size_t block_size_;
      size_t size_;
    
    
    public:
      Container(void) {
        std::cout << "Constructing the Container..." << std::endl;
        block_size_ = 16;
        size_ = 0;
        free_list_.reserve(block_size_);
    
    
        try {
          blocks_.push_back(std::unique_ptr<Block<T>>(new Block<T>(block_size_)));
    
    
          Block<T> &block = *blocks_[0];
    
    
          for (size_t i = 0; i < block.size(); ++i)
            free_list_.emplace_back(block.data() + i);
        }
        catch (std::exception &e) {
          std::cout << e.what() << std::endl;
        }
      }
    
    
      template<class... Args> 
      Element<T>* insert(Args&&... args) {
        std::cout << "Inserting..." << std::endl;
        try {
          Element<T>* element = new(free_list_.back()) Element<T>(args...);
          ++size_;
    
    
          free_list_.pop_back();
          
          return element;
        }
        catch (std::exception &e) {
          throw e;
        }
      }
    };
    
    
    #endif
    main.cpp
    Code:
    #include <iostream>
    #include <stdexcept>
    #include <string>
    
    
    #include "container.hpp"
    
    
    class Test {
    private:
      std::unique_ptr<int[]> data_;
      int x_;
    
    
    public:
      Test(int x) {
        std::cout << "Attempting to construct Test::Test(int)" << std::endl;
        data_ = std::move(std::unique_ptr<int[]>{new int[16]});
    
    
        if (x == -1) {
          x_ = x;
          return;
        }
    
    
        throw std::invalid_argument("Invalid value passed to Test!");
      }
    };
    
    
    int main(void) {
      // Container<int> c;
    
    
      // for (int i = 0; i < 8; ++i) {
      //   auto elem = c.insert(i);
      //   std::cout << elem->value() << std::endl;
      // }
    
    
      Container<Test> c;
    
    
      try {
        c.insert(3);  
      }
      catch (std::exception &e) {
        
      }
    
    
      return 0;
    }
    I'm kind of new to all of this stuff so any advice from anyone would be much appreciated! I'm looking at you, Elysia and laserlight. And maybe Yarin too. I count on you guys lol.

  8. #38

  9. #39
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    I'll read up on that more but I think I might be too stupid for that example lol.

  10. #40
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Okay, I read that article some more but I'm confused. How does overloading the new operator help me? Won't I still have to basically do what it is i am doing now?

  11. #41
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Lol okay, I read the page in more depth and the author references a fixed-size allocator but I can't seem to find much information on what's a good implementation.

    I realize though that the article you linked to, Codeplug, is pretty good. I should be hiding the implementation of requesting memory. It's a neat design pattern. The only problem is, I'm not sure where to go from here with regards to implementing the allocator.

    I like CGAL's idea of using a system of increasingly larger pools of memory linked together so that the container is at the least iterable. I don't care about allocator-awareness or anything like that. This can be locked to one allocator.

    So, for a fixed-size allocator, I want a chunk of blank memory that's aligned to the datatype that I'm passing in.

    Can I honestly just do something like,
    Code:
    void *memory_pool_ = malloc(proposed_number_of_elements * sizeof(T));
    and then have all new() calls return a valid, aligned address of the memory_pool_?

  12. #42
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> char buffer_[sizeof(T)];
    Why not just "T t_"?

    gg

  13. #43
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    I think because with that way, the constructor is invoked. With chars, I have the ability to separate allocation from initialization.

  14. #44
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    I've used memory pools for this sort of functionality in the past. You allocate "blocks" of memory from new, so you still have cache locality.

    So instead of "T t_" you'd have "T *pt_".

    gg

  15. #45
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Do you have the code or any examples then? I'm really curious to see how other people have done this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Is this thread safe?
    By theoobe in forum C# Programming
    Replies: 2
    Last Post: 09-22-2012, 02:27 AM
  2. Thread-Safe Functions
    By scioner in forum C Programming
    Replies: 6
    Last Post: 04-17-2008, 11:32 PM
  3. Safe Thread Queue
    By mauricio.sch in forum C++ Programming
    Replies: 5
    Last Post: 01-29-2008, 06:19 PM
  4. Is DrawDibDraw thread safe?
    By vart in forum Windows Programming
    Replies: 0
    Last Post: 11-14-2006, 11:53 PM
  5. Is this thread safe
    By Bru5 in forum C++ Programming
    Replies: 5
    Last Post: 06-23-2006, 05:34 PM