C++ threading question.

Google for MPMC ring buffer.

In read part you just waiting for non-empty condition

Lockfree is a serious pain to get correct so I don't suggest doing it yourself. I would point out the moodycamel (https://github.com/cameron314/concurrentqueue) implementation as something which has been well debugged and tested. Having used this in heavily contentious situations, I would say that it is exceptionally fast and so far bug free.

15 hours ago, Makusik Fedakusik said:

Google for MPMC ring buffer.

In read part you just waiting for non-empty condition

Thanks I'll check it out.

14 hours ago, All8Up said:

Lockfree is a serious pain to get correct so I don't suggest doing it yourself. I would point out the moodycamel (https://github.com/cameron314/concurrentqueue) implementation as something which has been well debugged and tested. Having used this in heavily contentious situations, I would say that it is exceptionally fast and so far bug free.

I'm sure it's great but I'm not sure I can use it. My objects are in a specialized heap with 32 bit 8 byte aligned pointers and reference counting. in the description, it claims to do it's own memory management. I'll have to look at in detail to see if things are compatible. Thanks for the tip though.

I'm using just a set of atomic pointers in my implementation on a fixed size statick heap memory block and small spin-locking

#define RawSpinLock(__lock) { while (InterlockedExchange(&(__lock), 1)) while (__lock) {} }
#define RawSpinUnlock(__lock) { InterlockedExchange(&(__lock), 0); }

template<typename T, int size> struct ThreadPoolBuffer
    {
		public:
			/**
			 Class constructor
			*/
			inline ThreadPoolBuffer() : writePtr(0), writeLock(0), readPtr(0), readLock(0) { }
			/**
			 Class destructor
			*/
			inline ~ThreadPoolBuffer()
			{ }

			/**
			 The ammount of elements contained
			*/
			api uint32 Size() const;

			/**
			 Determines if there are elements left
			*/
			inline bool Empty() const { return (readPtr == writePtr); }

			/**
			 Tries to insert the given element at the bottom of this list
			*/
			api bool Enqueue(T const& entity);
			/**
			 Tries to return the first element at the top of this list
			*/
			api bool Dequeue(T& entity);

			/**
			 Clears the buffer non-thread-safe
			*/
			inline void Clear()
			{
				writePtr = 0;
				writeLock = 0;
				readPtr = 0; 
				readLock = 0;
			}

		protected:
			T buffer[size];
			strict uint32 writePtr;
			strict uint32 writeLock;
			strict uint32 readPtr;
			strict uint32 readLock;
    };

template<typename T, int size> uint32 ThreadPoolBuffer<T, size>::Size() const
	{ 
		#define MASK (size - 1u)

		const uint32 reader = CompareExchange32(const_cast<uint32*>(&readPtr), 0, 0);
		const uint32 writer = CompareExchange32(const_cast<uint32*>(&writePtr), 0, 0);
		return ((reader > writer) ? (size - reader + writer) : (writer - reader));

		#undef MASK
	}

	template<typename T, int size> bool ThreadPoolBuffer<T, size>::Enqueue(T const& entity)
	{
		#define MASK (size - 1u)

		RawSpinLock(writeLock);
		const uint32 current = writePtr;
		const uint32 next = current + 1;
		const uint32 reader = CompareExchange32(const_cast<uint32*>(&readPtr), 0, 0);

		if(((reader > current) ? (size - reader + next) : (next - reader)) > MASK)
		{
			RawSpinUnlock(writeLock);
			return false;
		}

		buffer[current] = entity;
		Exchange32(&writePtr, next & MASK);
		RawSpinUnlock(writeLock);
		return true;

		#undef MASK
	}

	template<typename T, int size> bool ThreadPoolBuffer<T, size>::Dequeue(T& entity)
	{
		#define MASK (size - 1u)

		RawSpinLock(readLock);
		const uint32 current = readPtr;
		RawSpinUnlock(readLock);
		
		if(current == CompareExchange32(const_cast<uint32*>(&writePtr), 0, 0))
			return false;

		entity = buffer[current];
		bool result = true;

		RawSpinLock(readLock);
		if (readPtr != current) result = false;
		else Exchange32(&readPtr, (readPtr + 1) & MASK);
		RawSpinUnlock(readLock);

		return result;

		#undef MASK
	}

The only clue here is that the buffer needs a size of power of two or leads to wrong behavior but I used it in my fiber task pool implementation with success

I actually discovered atomic<>.compare_exchange_weak after I posted this thread. It seems (i hope) to solve my problems but I haven't tested anything yet, and I'm aware that once you go beyond basic threading stuff, it can be hard to get things to work properly. In any case I'm going to give it a shot and if it fails I'll check out the solutions here more thoroughly. In general I prefer to understand what's going on under the hood if I can.

If you don't want to use a pre-built lock free queue, I'd suggest starting with a combination of a mutex and a semaphore. Unless the functions are very quick to execute then there shouldn't be much contention on the mutex anyway.

The the semaphore is needed to keep track of how many items are in the queue so you don't need to poll - the worker threads simply wait on the semaphore, and then remove an entry from the queue, and the main thread signals the semaphore whenever it adds an item to the queue.

Even if you had a lock free queue instead of one using a mutex, you'd probably still want the semaphore to avoid the need for polling to see if there's anything in the queue.

My advice is not to optimize something when you don't know if you need to. If the locks are so expensive for you, it might be a good indication that the jobs that you are trying to parallelize are too small. You'll probably incur greater penalties from getting data to and from the consumer thread to the worker threads.

I would profile a standard implementation before trying to design something from scratch.

10 hours ago, costin said:

My advice is not to optimize something when you don't know if you need to. If the locks are so expensive for you, it might be a good indication that the jobs that you are trying to parallelize are too small. You'll probably incur greater penalties from getting data to and from the consumer thread to the worker threads.

I would profile a standard implementation before trying to design something from scratch.

I'm 100% sure that's not true. The fractal functions are by far the most CPU intensive part of the code. That much I know from testing. As for the pipeline, it's easy enough to do with a mutex. But seeing as we are talking about a small piece of code, I don't see a problem tying to get make it lock free. If it doesn't work I can change it to use a mutix in 10 minutes.

17 hours ago, Gnollrunner said:

I'm 100% sure that's not true. The fractal functions are by far the most CPU intensive part of the code. That much I know from testing. As for the pipeline, it's easy enough to do with a mutex. But seeing as we are talking about a small piece of code, I don't see a problem tying to get make it lock free. If it doesn't work I can change it to use a mutix in 10 minutes.

For fractal calculations, you get much more out of your CPU by resizing your job batches (clusters of points instead of one point if this is what you are doing). Pulling jobs from a queue and executing them is an expensive operation (much more than a lock), and you get better return if you optimize your job sizes.

As for your synchronization implementation, you are basically using the same instructions that are used for implementing the locks.

I cannot count how many times I reinvented the wheel just to end up with... a wheel.

Based on the further description of the work, there is another option to consider: change where you are making the division between threads. A general rule of thumb here is that finding the most appropriate place to parallelize the code is the biggest bang for the buck. Now, if you look at most software renderers out there (similar problems), they perform parallelization based on screen tile divisions rather than attempting to parallelize the inner functionality. It is both a simple approach and generally the best performance because it removes a number of bottlenecks due to contention.

This would be my suggestion. Unfortunately fine grained threading of the level which is suggested is extremely difficult to make effective. At least 50% of the work going to a threaded architecture is choosing the level of distribution appropriate to the task. Generally speaking, the simplest solution which is effective is always the best starting point.

Perhaps I should describe a little of more what I’m trying to do here. First I want to tell a small story. A few months ago I was watching a YouTube video with Bjarne Stroustrup. I don’t even remember what it was about, but I remember something he said in a half joking manner. I’m heavily paraphrasing …… “10 threads all waiting on one”. That kind of stuck in my mind. So my main goal here is to keep all threads busy.

Now I’ll need to talk a bit more about how things work (although some of this is already in my blog). First this is for a voxel engine. My voxels are probably way different from those in most implementations. Each part is a different object. That means we have voxels, voxel walls, voxel edges, and voxel nodes.

This makes voxel subdivision and sharing of mesh vertexes very easy. In fact we never have to piece together the meshes from mesh triangles stored in each voxel after they are built, because the mesh vertexes are stored with voxel edges so they are shared with all possible voxels that need them. Meshes are built already completed in one step even though a voxel is a separate unit in an octree.

In order to re-chunk and re-voxelize the planet as a player moves around, we need to know the fractal/procedural values used by each corner node of a voxel. It’s not something we can really do in advance because until we know a player’s new position we don’t know what fractal/procedural data we need to calculate.

However because we are sharing data between voxels we need to store new voxel nodes generated from subdivided voxel edges and faces, in the edges and faces themselves. So that means we can pre-allocate voxel nodes and calculate their function values for the next possible level (or even two levels) down, while the build thread is working on other steps like building the actual mesh geometry and calculating normals.

My plan is to queue these voxel nodes on a pipeline and then have from 1 to N threads do the calculation. By doing it this way instead of splitting up the data up for separate threads, all threads are guaranteed to be running as long as there are voxel nodes in the queue. If I split it up, it means that threads can be idle which likely isn’t so efficient. This is especially true since different parts of the planet may require different functions to generate them.

First up, you're right that most don't do that because it generates an enormous amount of work.

The big benefit of voxel regions is that once they are figured out and loaded they don't need further processing. You've got a box figured out, don't re-compute it. There is (usually) no issue having adjacent voxels that appear continuous. If one of them is modified, you can make a matching adjustment to the neighbor if necessary, although that work can also generally be avoided by not making them rely on each other.

The typical approach is to pre-load or pre-compute data before the player reaches it. That can mean having a buffer of some distance around the player, and when the player moves toward the edge of the buffer, processing the next region off in the distance. By making your geometry depend on neighbors you're requiring far more work than is necessary.

Next regarding parallelism, You're right about having everything rely on a shared source being an issue.

In my experience the most useful method for parallelism has the PCAM initialism: Partition, Communication, Agglomeration, Mapping.

Partition the concepts into the smallest units of work. Don't think too much about your current implementation, think about the actual tasks being done which can be considered independent. Make sure all work is actually necessary, this is the place to eliminate tasks where possible.

Identify all the communication between units of work. Some units serve as sources or generators, others consumers, many are transformative taking both a source and a sink. Find them all, paying attention to natural communications bottlenecks.

Agglomerate, or form them into groups and clusters, focusing on their communications patterns. Chains of work and clusters of work tend to suggest natural boundaries. Hubs and spokes tend to suggest others. Often you can turn a cluster of tasks into hubs and spokes which tend to fit a master/worker model, or a parallel chains suggesting a producer/consumer model.

Map the clusters of work based on what fits the hardware model, focusing mostly on communication rates and bottlenecks. Bottlenecks can generally be addressed by exchanging time and space, but ultimately you reach hardware limits.

22 minutes ago, frob said:

First up, you're right that most don't do that because it generates an enormous amount of work.

The big benefit of voxel regions is that once they are figured out and loaded they don't need further processing.

I'm not sure what you you mean. In an octree implementation, voxels constantly change as you move around and so do chunks if you want to support chunking with planet size generation. Keeping the same chunk size would quickly become untenable. At distance your chunk could easily be below the pixel resolution. For this application I don't have the luxury of smog to hide stuff that is far away. If I'm on a mountain top I want to see the next mountain top that could be a 100 miles away

33 minutes ago, frob said:

The typical approach is to pre-load or pre-compute data before the player reaches it. That can mean having a buffer of some distance around the player, and when the player moves toward the edge of the buffer, processing the next region off in the distance. By making your geometry depend on neighbors you're requiring far more work than is necessary.

I think perhaps you may not be considering the scale involved. Again we are talking about a planet. My current test planet has a radius of 400 km that's a surface area of slightly over 2 million square km. The a coarsest resolution I'm targeting (.5 meters) that means the data would be 64 trillion bites with nothing but height map data and with a relatively small planet. Double the radius and it goes up astronomically . There is no way to store that size data on disk, so pre-load is out. As for pre-compute this is exactly what I'm doing. But even then "some distance" can be a 100 miles so you can't just compute all the data at a fixed resolution. Everything has to be LODed based on the square of the distance, so meshes must always be changing.

Also because you have LOD, geometry must depend upon neighbors. There is no way around that. This why people wrote stuff like this https://transvoxel.org/ although I don't use this particular algorithm. With dual contouring LOD is more automatic but still the voxel data is always dependent upon their neighbors.

So you want to see 100 miles away, or 160934 meters radius, meaning 81 billion square meters. At half-meter resolution, so you need to have 325 billion voxels ready for display, every frame.

What kind of supercomputer are you running on?

Games don't do planet scale because it doesn't make sense. If you want to do planet-wide simulations there are systems like NOAA doing weather forecasts, or geology folks studying the volume of the earth. But they are smart enough to realize processing takes hours or days, in addition to using much larger regions.

The largest scale games ever released have barely reached the hundred square miles milestone.

7 hours ago, Gnollrunner said:

Also because you have LOD, geometry must depend upon neighbors. There is no way around that.

But voxels can represent volume and bound with triangles to avoid visible cracks even if there is a resolution mismatch between chunks. With that functionality you would not need to constantly update everything as the player moves, you could just do time sliced updates of one chunk per frame for example. I think that's what @frob meant with 'no need for further processing (as long as its chunk LOD does not change)'.

Surely you have thought of this before. Why did you decide for constantly updating everything based on exact squared distance instead? (Assuming i get you right)

Edit: Assuming you want to hide popping transitions, would something like a progressive mesh be an option (i mean haveing two LODs per chunk, vertices can lerp from high LOD to low LOD on GPU based on exact distance)?

This way you have time sliced per chunk processing on CPU but no popping. The only problem i see is to make sure 2 LODs are always enough for a given chunk size and distance.

29 minutes ago, JoeJ said:

But voxels can represent volume and bound with triangles to avoid visible cracks even if there is a resolution mismatch between chunks. With that functionality you would not need to constantly update everything as the player moves, you could just do time sliced updates of one chunk per frame for example. I think that's what @frob meant with 'no need for further processing (as long as its chunk LOD does not change)'.

Surely you have thought of this before. Why did you decide for constantly updating everything based on exact squared distance instead? (Assuming i get you right)

Edit: Assuming you want to hide popping transitions, would something like a progressive mesh be an option (i mean haveing two LODs per chunk, vertices can lerp from high LOD to low LOD on GPU based on exact distance)?

This way you have time sliced per chunk processing on CPU but no popping. The only problem i see is to make sure 2 LODs are always enough for a given chunk size and distance.

First off the chunks change all the times. There is really no avoiding it when you are doing large scale stuff. If you are saying they don't need to update every frame, yes of course. I take the position of the player and update any chunks that change from the players old . The others are left as they are except for border voxels where a change resolution has to be compensated for.

As for pooping my meshes are tagged with new, old and dying. So the idea is just to fade in new chunks, swap rendering order and fade out the old. To be fair I'm still debugging with wire frame so I have yet to test it.

Another thing is filling cracks using skirts can be visible, you can try to hide them with shading but there is still somewhat of a geometry discontinuity. I see no reason use them when there are other options that avoid the discontinuity. In any case chunks or not, where you have one voxel next to higher resolution voxels you will have cracks and you have to fix those somehow unless you are doing surface nets or dual contouring. If are using those, there are other issues to contend with like non-manifold geometry and also the fact that your geometry crosses voxel boundaries. I believe Voxel Farm uses dual contouring and perhaps that's a reasonable solution but I have yet to see a game actually working with it and also I haven't found information on the scale it supports.

For me I'll probably implement an extended marching algorithm to support sharp edges at some point. That seems to have some of the advantages of both marching cubes and duel contouring.

1 hour ago, frob said:

So you want to see 100 miles away, or 160934 meters radius, meaning 81 billion square meters. At half-meter resolution, so you need to have 325 billion voxels ready for display, every frame.

What kind of supercomputer are you running on?

You are completely ignoring LOD. Why? Have you seen the last entry in my blog? Of course it's a work in progress but I think it's clear it's likely doable. At this stage it's using one build thread and one render thread on an 8 year year old computer. It's also gotten a lot faster since the video just by eliminating the back side of the planet and also eliminating voxels so high above the geometry, they they are irrelevant. The next optimizations will be the pipeline and something I won't discuss right now because it requires a lot more explanation.

1 hour ago, frob said:

Games don't do planet scale because it doesn't make sense.

Why? I'm not sure how you can make such a blanket statement. There is already No mans sky and I am certainly not the only person working on planetary engines. There are Dual Universe and Star Citizen too...

47 minutes ago, Gnollrunner said:

Another thing is filling cracks using skirts can be visible

Just to make sure you get me right see this image:

There would be no need for skirts even for disconnected geometry.

But now i realize you would need 3 LODs not just 2, which makes it a lot less attractive

3 minutes ago, JoeJ said:

Just to make sure you get me right see this image:

There would be no need for skirts even for disconnected geometry.

But now i realize you would need 3 LODs not just 2, which makes it a lot less attractive

Is this voxel related? I'm a bit confused here. LOD with voxels is somewhat of a different animal than regular mesh LOD.