It sometimes can't be helped, but in most cases you can have many objects in the same texture (within reason).
So, while I've made many renderers in my time, right now I'm making a 2D game.
And for each layer in my game, I have to sort by each objects sorting mechanism, eg. by the bottom end of the sprite as its drawn.
For that to happen, I have to sort by layer then by texture and then by its sorting mechanism.
It ended up being pretty fast, much faster than I thought it would be
I have a class that contains all renderable/visible objects in a specific layer, eg. a wrapper for a vector, then under that I have a class that represents sorted sprites (another wrapper for a vector).
Lots of dynamic allocation, except it only happens until the vectors reach a certain growth level, then they stop growing. The allocations stop, and even after new frame begins nothing is going to be allocated again unless I spam even more objects.
So, vector of layers which contain vector of sprites. Each sprite know their texture, but they also have a drawing order. I sort by that drawing order, then by texture. It works out OK in the end.
After all that is done, I generate vertices for everything and set markers for when I need to change texture.
Then I upload ALL the vertices once (DYNAMIC_DRAW), and render in the given order by changing texture as needed.
I basically stream data from CPU to GPU, and it's working pretty well for me.
In my case the objects are pretty static (they are sprites,) but even so, I gain alot by simply generating them on the fly, and rendering as much as possible in one go.
My reasoning for different textures is simply for convinience. The textures represents sprites that differ greatly in functionality in my game.
Maybe for you the textures are unique per object, something that you should avoid if you can.
In my case, I could probably live with a single texture, but it's also a matter of making life easier.
Btw. Are you sure you have a performance issue? And if so, are you sure it's where you think it is? Any data?
1. Don't worry about switching textures, as long as you are not overdoing it. Do some profiling to make sure you need to do it, if you think you do.
2. In a 2D game you can probably use a megashader to avoid ever changing shader. That means you can more easily sort by texture where needed.
3. You need to know the sizes of your textures to generate proper texcoords. It's not always possible to use Texture Arrays, so sometimes you just have to do it the old-fashioned way where you subtract 1/2 to 1/64th of a pixel to avoid pixel bleeding.