I'm doing a lot of sorting and looping through std::vector inside of my render loop but I need help optimizing it.

I'm doing tests using around a 1000 objects.

If I run it like this (which works the way I want it to) it takes much too long.

On my computer (fairly recent quad core intel cpu) this takes 1.25ms to run !

Release mode and using

#define _SECURE_SCL 0

#define _HAS_ITERATOR_DEBUGGING 0)

Now if I were to comment out the most time consuming part which is the one I've marked with X down below

I can get it down to around 0.51ms, which is still too slow and doesn't work as intended.

Can someone help me make this faster ? :/

void RendererContext::CreateDrawCalls(std::vector<SceneEntityDescription> &entities,
									  std::vector<unsigned int> &opaque_drawcalls,
									  std::vector<unsigned int> &transparent_drawcalls,
									  std::vector<InstanceGroupDescription> &instanceGroups)
{
	// Depth sort entities
	std::vector<DepthOrderedObject> depthValues;
	depthValues.reserve(entities.size());
	float camPosZ = XMVectorGetZ(this->perspectiveCamera->Position());
	for(size_t i = 0; i < entities.size(); ++i)
	{
		DepthOrderedObject obj;
		obj.depthValue = entities.worldPosition.z - camPosZ;
		obj.index = i;
		depthValues.push_back(obj);


		// Create InstanceGroup if it doesn't already exist
		if(instanceGroups.size() > 0)
		{
			if(entities.ID < instanceGroups.size())
			{
				// This means the instance group already exists
				// so increase its numInstances
				instanceGroups[entities.ID].numInstances++;
			}
			else
			{
				// If the instance group doesn't exist,
				// create it
				InstanceGroupDescription instance;
				instance.entityType = entities.entityType;
				instance.numInstances = 1;
				instance.instanceID = entities.ID;
				instanceGroups.push_back(instance);
			}
		}
		else
		{
			// This means we've got no instance group yet
			// so just create the first one
			InstanceGroupDescription instance;
			instance.entityType = entities.entityType;
			instance.numInstances = 1;
			instance.instanceID = entities.ID;
			instanceGroups.push_back(instance);
		}

	}

	// Sort depth values
	std::sort(depthValues.begin(), depthValues.end(), FrontToBackSort);

	bool sortOpaqueDrawCalls = false;
	bool sortTransparentDrawCalls = false;

	// Create Draw Calls
	for(size_t i = 0; i < entities.size(); ++i)
	{
		// MSB part (Depth ordering)
		unsigned int drawCall = 0;
		drawCall = i;
		drawCall <<= 16;

		//// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
		// Search for the index of our sorted depth array
		for(unsigned int u = 0; u < depthValues.size(); u++)
		{
			if(depthValues.index == i)
			{
				// Add depth value to our draw call
				drawCall = u;
				drawCall <<= 16;
			}
		}
		//// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

		// LSB part (instance group)
		// Search for the index of our instance groups
		for(unsigned int v = 0; v < instanceGroups.size(); v++)
		{
			if(instanceGroups[v].instanceID == entities.ID)
			{
				// We've found the instance ID corresponding to this
				drawCall += v;
				break;
			}
		}

		if(entities.material.type != MaterialTypes::Transparent)
		{
			// If the draw call doesn't already exist
			if(this->previous_opaque_drawcalls.size() > 0 &&
			  (i < this->previous_opaque_drawcalls.size()))
			{
				// If this draw call isn't the exact same as last frame
				// update it
				if(drawCall != this->previous_opaque_drawcalls)
				{
					sortOpaqueDrawCalls = true;
					this->opaqueDrawCallsDirty = true;
					opaque_drawcalls.push_back(drawCall);
				}
			}
			else
			{
				this->opaqueDrawCallsDirty = true;
				sortOpaqueDrawCalls = true;
				opaque_drawcalls.push_back(drawCall);
			}
		}
		else
		{
			// If the draw call doesn't already exist
			if(this->previous_transparent_drawcalls.size() > 0 &&
			  (i < this->previous_transparent_drawcalls.size()))
			{
				// If this draw call isn't the exact same as last frame
				// update it
				if(drawCall != this->previous_transparent_drawcalls)
				{
					this->transparentDrawCallsDirty = true;
					sortTransparentDrawCalls = true;
					transparent_drawcalls.push_back(drawCall);
				}
			}
			else
			{
				this->transparentDrawCallsDirty = true;
				sortTransparentDrawCalls = true;
				transparent_drawcalls.push_back(drawCall);
			}	
		}
	}


	// Sort Draw Calls
	//--------------------------------------
	if(sortOpaqueDrawCalls)
	{
		std::sort(opaque_drawcalls.begin(), opaque_drawcalls.end());
	}	
	
	if(sortTransparentDrawCalls)
	{
		std::sort(transparent_drawcalls.begin(), transparent_drawcalls.end());
	}
}

Well in the first loop I'm calculating the actual depth of the object and store it inside a new vector, which I can then sort by the depth.

After that I've got the depth values themselves sorted but the problem is I don't know which depth value belongs to which entity....

I need the sorted order as indices from 0 - XXX to store inside my unsigned integer for the draw call.

I can't just put the actual floating point depth value (which could very well be negative!) inside the 16bit part of an unsigned integer right ?

Store a pointer to the entity in the struct you sort...

I can't create the draw call at the same time as the rest inside the first loop since I have to run through everything and then sort first.

After that I can create my draw call for every entity I have.

And when I run through that I need to know the ordered depth value index that corresponds to this entity...

...or maybe I have to do this entirely different....I have no idea though..

It's possible for the position of an object to be behind the camera but at least part of the object to be in front of the camera.

The origin of my sofa is behind me but I can still see the arms ;)

You need to check some bounding volume (sphere, AABB, OBB, whatevs) not just a single point.

What do you mean by "way before you start rendering or even going through the entity lists". Do you mean the draw call is being created at the time of asset creation ? And you'd then update the draw calls whenever something changes like the object is moving ?
And about the depth I'd still need to sort the depth before I can submit it's index order to the (unsigned int) key of my draw call or not ?

Btw I'm already eliminating objects not seen by the camera using view frustum culling and AABBs.

update: I'm going to simplify this process a bit, which I think will work in my case.