Jump to content

  • Log In with Google      Sign In   
  • Create Account


rip-off

Member Since 16 Mar 2005
Offline Last Active Today, 11:34 AM
*****

#5141338 C++ c

Posted by rip-off on 22 March 2014 - 07:11 PM

Even though I probably wont use the class anymore, did I get it right now?

Obviously the class does not yet comply with the rule of three, I won't discuss this further other than to add that a simple "quick fix" is to make the class noncopyable by declaring a private, unimplemented copy constructor and assignment operator. This technique will mean you get a compile error if client code tries to copy/assign the class, and a link error if the class itself performs these operations. In C++11, I believe there is new syntax to suppress automatic generation of such functions, but I don't much practical experience with this so I won't say more.

You appear to have a bug in the last full code you posted, where isUsed is not updated if removeElement() is called.

I'd recommend at least using an assertion that isUsed[index] is true in both getElement() and removeElement().

The freeElementList and isUsed are similar arrays that are almost always accessed together, so one idea might be to have an internal struct containing both pieces of information and allocate a single array of that type. This would reduce the number of allocations required. However, I believe in this specific case you could avoid keeping both pieces of information by choosing a marker value, for example -1, to include in the freeElementList to indicate that the element is in use.

In fact, the "similar arrays" argument is true of the data instances themselves, one alternative implementation is to have an internal structure containing the potentially uninitialised data and . However, leaving it separate may have cache benefits depending on how frequent accesses are versus removals.

In the case where all members are moved to a single structure, there is no reason not to implement your class in terms of std::vector, this would simplify a lot of manual work and reduces your class to the essentials of managing the free list. If the class is to maintain the element array separate from the used/next array(s), then you could still implement in terms of std::vector with some relatively minor memory overhead (each vector would maintain the element count and capacity separately).

The addElement function doesn't gracefully handle exceptions thrown when allocating the storage or copying the elements. It both leaks memory and can leave the object in an inconsistent state. The constructor can leak if an exception throws during allocation. Implementing in terms of a single std::vector should avoid these issues, implementing in terms of multiple std::vectors would still require care.

It is typical for such containers to have a const and non-const accessors. The convention would be the const version returns a const reference, and the non-const version returns a mutable reference - unless by necessity or design the elements should not be mutable (e.g. the key in std::map is not mutable in isolation - allowing this could corrupt the map ordering).

My C++ skills are rusting of late, but I believe this is in the ballpark of an implementation in terms of std::vector:
template <typename T>
class Vector
{
private:
	struct Element {
	private:
		static const int ELEMENT_IN_USE = -1;
		int nextFreeIndex;
		char storage[sizeof(T)];
	public:
		Element(int index) {
			nextFreeIndex = index + 1;
		}

		~Element() {
			if(isUsed()) {
				object().~T();
			}
		}

		Element(const Element &other) {
			if(other.isUsed()) {
				new(storage) T(other.object());
			}
			nextFreeIndex = other.nextFreeIndex;
		}

		int initialise(const T &data) {
			assert(!isUsed());
			int result = nextFreeIndex;
			new(storage) T(data);
			nextFreeIndex = ELEMENT_IN_USE;
			return result;
		}

		void clear(int freeIndex) {
			assert(isUsed());
			object().~T();
			nextFreeIndex = freeIndex;
		}

		T &object() {
			assert(isUsed());
			return *reinterpret_cast<T*>(storage);
		}

		const T &object() const {
			assert(isUsed());
			return *reinterpret_cast<const T*>(storage);
		}

		bool isUsed() const {
			return nextFreeIndex == ELEMENT_IN_USE;
		}
	private:
		// TODO: do I need this guy?
		Element &operator=(Element copy);
	};

	int freeIndex;
	std::vector<Element> elements;
public:
	Vector(int initialCapacity) : freeIndex(0) {
		elements.reserve(initialCapacity);
		for(int i = 0 ; i < initialCapacity ; ++i) {
			elements.emplace_back(i);
		}
	}

	int addElement(const T& element) {
		int currentSize = elements.size();
		if(freeIndex > currentSize) {
			int newSize = currentSize * 2;
			elements.reserve(newSize);
			for(int i = currentSize ; i < newSize ; ++i) {
				elements.emplace_back(i);
			}
		}

		int resultIndex = freeIndex;
		Element &target = elements[freeIndex];
		freeIndex = target.initialise(element);
		return resultIndex;
	}

	void removeElement(int index) {
		assert(index < elements.size());
		elements[index].clear(freeIndex);
		freeIndex = index;
	}

	T getElement(int index) {
		assert(index < elements.size());
		return elements[index].object();
	}

	const T &getElement(int index) const {
		return elements[index].object();
	}

private:
	// Noncopyable: deliberately private & unimplemented
	Vector(const Vector &);
	Vector &operator=(const Vector &);
};



#5140341 Could someone explain this?

Posted by rip-off on 19 March 2014 - 10:09 AM

Everyone back on topic, please. I won't ask nicely again.

 


I just thought the name would have more important in a main function and it used a lot.

They're important, yes. Names are vital to communicate intent to other programmers. Hence, dyou certainly shouldn't take Hodgman's suggestion of Sally too seriously!

 

But funnily enough C++ does not require that the names match between declarations and definitions.

void example(int one, int two);
 
int main()
{
    example(42, 13);
}
 
void example(int a, int b)
{
    std::cout << "A: " << a << ", B:" << b << std::endl;
}

 

In fact, you don't need to provide names when declaring a function, and if you don't wish to use a parameter you don't need to give it a name in a definition:

void example(int, int);
 
int main()
{
    example(42, 13);
}
 
void example(int a, int)
{
    std::cout << "A: " << a << ", but we don\'t care about B..." << std::endl;
}

It is typical for them to be present and to match, again to help provide clarity.

 
Thus, to the code that "calls" main, i.e. the runtime, it doesn't matter what the parameters names are or if they even have names.



#5140257 Shader Linkage Error

Posted by rip-off on 19 March 2014 - 02:32 AM

You already have a very recent thread about this, please be patient.


#5140256 OpenSSH on windows

Posted by rip-off on 19 March 2014 - 02:30 AM

Please don't redact your post like that. The preferred approach is to reply to the thread with the solution you found. This allows others to learn from your question, and also means that someone else might chime in with an alternative solution that is better or easier, or just interesting.


#5138088 Classes and Objects

Posted by rip-off on 11 March 2014 - 07:01 AM

Those classes looks like a good start.

 

The first thing I'd ask you to think about is the class suffix. For example, std::string is a class but it isn't called std::stringClass. Consider simple class names like "player", "monster" and "item". A common convention is to use Uppercase for class names, so Player - and lowercase for function and variable names, so "Player player" or "Monster pig".

 

The next thing to think about is maybe using constructors instead of having setters for all the fields. One problem with adding setters is that it can break encapsulation and defeat the purpose of making all the fields private.

 

Also, consider adding member functions for interesting properties that aren't exactly fields. For example, you're checking if a monster is alive by testing whether it's HP is greater than zero.  You can encapsulate this logic by adding a member function, bool isAlive(), and then the client code doesn't need to worry about the Monster's HP directly.




#5135870 Memory overwrite after allocating 4k ints

Posted by rip-off on 02 March 2014 - 11:29 AM

Im basically forcing the class to work inside vectors. (that Im assuming to require a copy ctor)

In C++ parlance, std::vector requires that the object it stores are copyable. std::vector expects to be able to copy objects as it reallocates or if existing objects are added to it.

So yes, you'll need to ensure you are correctly handling the rule of three in order to use it with std::vector.

Yeah, but the issue is knowing when you going to need it...

C++ is a value oriented language by default. This means that unless you take care, C++ is going to create copies of things. In addition, as you found out here, C++ is going to generate copy constructors (and assignment operators) where possible to enable this behaviour.

As a result, you'll almost always need to think about whether you want to allow copying your classes. For simple classes like a Vector3, copying is perfectly reasonable behaviour. For "large" objects (either with lots of members, or where the members are large dynamic allocations) you probably want to be very careful about when you actually copy them. For instance, having a noncopyable implementation with an explicit member function to copy where really necessary. You should note that polymorphic objects also need a lot of care if you really need them to be copyable.


#5132763 This may sound stupid ... [multitasking]

Posted by rip-off on 19 February 2014 - 03:38 PM

In fact, it looks like it isn't suspended at all.

That is the idea!

Threads can run for up to a time slice / quantum before the OS decides what to run next. You might have 618 threads, but not all are equal. There is priority, high priority threads will run more often than low priority threads. Some threads might be blocked, waiting on I/O or other signal - these will not be considered for scheduling until the I/O completes or signal is triggered. Even if one of the 618 threads is runnable, but only has less than a millisecond of work to do, it will release the time slice / quantum early (typically by blocking, but potentially just by yielding the processor), and the OS will pick another thread immediately.

Try starting a number of instances of your program, they'll eventually fight one another for processor time.


#5131751 Calling a virtual function, illegal call of non-static member function?

Posted by rip-off on 16 February 2014 - 11:48 AM

I suppose this will also work?

That should work.

The linker starts complaining about undefined external.

 
Without seeing the code and error messages, it is hard to be sure, but I would guess that the issue might be that you kept the implementation of the template in a source file. Unfortunately, C++ templates don't play nicely with such a setup.
 
You have three choices:
  • Place the implementation directly in the header file, either inline in the class declaration or just underneath the class.
  • If you prefer to have the implementation in a separate file for ease of browsing and maintenance, you can have a some_template.hpp.impl file, and #include it in some_template.hpp (there is no special significance to the file extension here).
  • At the end of the existing template source file, explicitly instantiate the template with each type you want to use.
I believe the first two approaches are the most common.


#5131698 Calling a virtual function, illegal call of non-static member function?

Posted by rip-off on 16 February 2014 - 07:05 AM

The race is between the lifetime of the WorkerThread and the start of the ThreadRountine. If the WorkerThread object was destroyed before the ThreadRoutine gets to create a copy of the shared_ptr, then you lose!

 

One way to avoid it might be like so:

class ThreadSafeCommunication
{
    // ...
    std::shared_ptr<ThreadSafeCommunication> self;
};
 
class WorkerThread
{
    WorkerThread()
    {
        spInterface = std::make_shared<ThreadSafeCommunication>();
        spInterface->self = spInterface;
        hThread = CreateThread(NULL, 0, WorkerThread::ThreadRoutine, spInterface.get(), NULL, NULL);
    }
 
    // ...
 
private:
 
    // ...
 
    static DWORD WINAPI ThreadRoutine(LPVOID param)
    {
        ThreadSafeCommunication *communication = static_cast<ThreadSafeCommunication*>(param)
        std::shared_ptr<ThreadSafeCommunication> spInterface;
        std::swap(spInterface, communication->self);
 
        while(!spInterface.unique())
        {
            // ... 
        }
 
        return 0;
    }
};

This scheme will keep the ThreadSafeCommunication instance alive even if the WorkerThread has been destroyed in the mean time.




#5130299 Thread-safe unique sequential index per class

Posted by rip-off on 10 February 2014 - 09:03 AM

The documentation for the java.util.concurrent package states:


Memory Consistency Properties

Chapter 17 of The Java™ Language Specification defines the happens-before relation on memory operations such as reads and writes of shared variables. The results of a write by one thread are guaranteed to be visible to a read by another thread only if the write operation happens-before the read operation. The synchronized andvolatile constructs, as well as the Thread.start() and Thread.join() methods, can form happens-before relationships. In particular:

  • Each action in a thread happens-before every action in that thread that comes later in the program's order.
  • An unlock (synchronized block or method exit) of a monitor happens-before every subsequent lock (synchronized block or method entry) of that same monitor. And because the happens-before relation is transitive, all actions of a thread prior to unlocking happen-before all actions subsequent to any thread locking that monitor.
  • A write to a volatile field happens-before every subsequent read of that same field. Writes and reads of volatile fields have similar memory consistency effects as entering and exiting monitors, but do not entail mutual exclusion locking.
  • A call to start on a thread happens-before any action in the started thread.
  • All actions in a thread happen-before any other thread successfully returns from a join on that thread.

The methods of all classes in java.util.concurrent and its subpackages extend these guarantees to higher-level synchronization. In particular:

  • Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread.
  • Actions in a thread prior to the submission of a Runnable to an Executor happen-before its execution begins. Similarly for Callables submitted to an ExecutorService.
  • Actions taken by the asynchronous computation represented by a Future happen-before actions subsequent to the retrieval of the result via Future.get() in another thread.
  • Actions prior to "releasing" synchronizer methods such as Lock.unlock, Semaphore.release, and CountDownLatch.countDown happen-before actions subsequent to a successful "acquiring" method such as Lock.lock, Semaphore.acquire, Condition.await, and CountDownLatch.await on the same synchronizer object in another thread.
  • For each pair of threads that successfully exchange objects via an Exchanger, actions prior to the exchange() in each thread happen-before those subsequent to the corresponding exchange() in another thread.
  • Actions prior to calling CyclicBarrier.await and Phaser.awaitAdvance (as well as its variants) happen-before actions performed by the barrier action, and actions performed by the barrier action happen-before actions subsequent to a successful return from the corresponding await in other threads.

The implementation of ConcurrentHashMap must do whatever it needs under the hood to ensure these properties.




#5130250 Thread-safe unique sequential index per class

Posted by rip-off on 10 February 2014 - 04:50 AM

I know what you're trying to do, it is called double checked locking, and unfortunately it is not guaranteed to work in Java. The synchronized keyword is not just a lock, it also inhibits certain optimisations that would be correct in single threaded code but that can cause issues in the presence of concurrency.

 

In addition, it is explicitly stated that HashMap is unsafe to read while another thread is updating it:


Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.)

 

A concurrent hash map has the properties you need.


Now the thing is ConcurrentHashMaps solve the access thing, but not the whole other operations I need to do. Say that I remove the synchronization and replace the HashMaps with Concurrent ones:

You don't remove the synchronized block - you still need that as you correctly point out. However, by using a ConcurrentHashMap with the synchronized block, you can get the lock-free optimisation you are trying to implement, in a way that is guaranteed to work.




#5130154 Thread-safe unique sequential index per class

Posted by rip-off on 09 February 2014 - 03:50 PM

It is not thread safe to access a variable like resolvedMap like that, where some access is synchronized and others are not. Even though some operations are "reads", you cannot guarantee the state is safe to read from if another thread is changing the state. Also, there is multi-processor consistency, to ensure other processors will see the changed value.

 

ConcurrentHashMap is lock free in the way you appear to be looking for:


However, even though all operations are thread-safe, retrieval operations do not entail locking, and there is not any support for locking the entire table in a way that prevents all access.




#5128009 My singleton class is not so singleton

Posted by rip-off on 01 February 2014 - 01:47 PM

Post a complete program demonstrating the behaviour.

 

Mandatory comment about singletons being overrated and overused...




#5127761 Find Min with Recursion

Posted by rip-off on 31 January 2014 - 10:28 AM


// returns -1 for an empty input

It would, if the test were n <= 1.




#5127727 Find Min with Recursion

Posted by rip-off on 31 January 2014 - 08:08 AM

Note that returning the index instead of the value can be a good solution. You can handle an empty array by returning an invalid index, such as -1 or N, but client code can still quickly get the value by using the index. For more general searching algorithms, this can handle the case where no matching element is found, too.






PARTNERS