Yes, but you can also play around with it. x,y maps to u,v where t is a constant that may be animated and you can use many functions. Nice to build intuition. Here is an example:
Because there are an infinite number of half-breed data structures that you could think of to balance tradeoffs.
The STL has to restrict itself to somewhat stereotypical data structures that are intuitive to understand, yet can be composed to create such tailored data structures.
What you suggest is basically a tradeoff for speed of front removal against wasting some memory.
There are an infinite number of such subtle tradeoffs that can be done. Some line need to be drawn somewhere.
The STL is not intended to contain all possible variants of data structures in existence. It should provide you with a minimal set of containers that are _good enough_ for most use cases. In the case where front insertion is important to you, you can use std::deque. If you want a mix of the pros and cons of deque and vector, then it's fair to say that's on you to implement it.
All the rest is for dedicated libraries / custom containers to implement.
The question the grandparent comment wrote was "Explain why popfront would not be implemented in the current vector in O(1) by simply pointing the front pointer forward one element?"
Answering that with "there are tradeoffs and STL had to pick one" is misunderstanding the point of this question; the _premise_ of the question is that there are tradeoffs and STL picked this one and we can safely assume they have some reason; the leading question is highlighting an interesting case where the tradeoff isn't trivially obvious regarding difficult-to-use capacity laying at the front of the vector after the popfront operation happens if you implement that operation in O(1).
I guess I still don't clearly see what the leading question is pointing at.
Should that be: _why was it not important to optimize for vector pop front?_
If that is the case, then I feel like the overall philosophy of vector vs deque answers that question.
Vectors are tailored to be good at random access and back insertion/removal, at the expense of wasting capacity.
Overall, that means vectors are focused for append-mostly workloads, thus why they often have and aggressive capacity reallocation factor.
Having a vector double down on unused capacity consumption by allowing constant time front removal was, I guess, deemed useless, since one would most likely be using a deque for such access patterns.
I'm thinking it's maybe it's "too obvious" for you that makes you misunderstand the point.
It's just:
- Look at these big-O, see that pop front isn't O(1)
- Here's a proposed pop front that is O(1) (move the pointer forward)
- Reason about why they didn't choose that.
It's already an aha moment for people to realize that the capacity left at front is generally harder to use than keeping unused capacity at the end. In the spirit of the leading question that aspect is something the reader can reasonably realize after thinking about it, not something that is intended to already be obvious before you start thinking.
because vectors are not designed for that. When they mean "dynamic" they literally just mean ontiguous memory, removing the first element would leave an empty space at the beginning. To maintain contiguity, all other elements would need to be shifted one position forward. This operation is linear in time complexity
O(n), as it depends on the number of elements in the vector.
Also Vectors manage their own memory allocation and deallocation. If the begin pointer is incremented without moving the elements, the vector would still be holding onto memory that it's not actually using for storage of active elements. This can lead to inefficient memory usage.
Basically speaking: they are designed to modify the end, keep adding, take a bit off, split them at a point, but not really take away from the beginning ( and I mean literally the first element)
If an STL container lacks a method, it's a hint that 'here be dragons'. For example, random access of a std::list: it's possible, but you don't want the uninformed to be doing it without considering the consequences simply because it's easy to write.
What do you do about the memory allocated for the first element? That's a decision for the programmer to think about, not for the standard to enforce. A std::deque may deallocate.
You're arguing that there aren't STL methods for doing inefficient things.
But the parent took that as a given. Their comment translates as, "why doesn't the STL allow efficient removal at the front of a vector" (which would be possible in principle, e.g. python bytearray is similar but supports it). Part of the answer is that it would need an extra internal data member.
BTW the pop on std::stack refers to the back so doesn't help with pop_front (and vector already supports pop_back).
Yes... But you don't need to memorize all this, and it leaves out a simple rule: vectors (or arrays) outperform everything else if the dataset is small. Small is usually in the order of 100-300, but can vary wildly.
Also note that all <algorithm>s have built-in fully automatic parallelism via <execution>, a massively underused feature. In typical CPP fashion though, their newer views:: counterparts lack those overloads for the moment.
You need to be aware that these invocations are going to blast your cores full throttle as you obviously don't have fine grained control. But as long as your data is easily parallelized on a vector with computations that don't depend on each other, it's a game changer. I use it all the time to multithread things with literally a single line of code.
I looked into it (my video, probably too long https://youtu.be/9oh66SF91LA?si=azDCSOAJKA9Gpzim), and the general result was that they make sense for non-small datasets and are a solid way to to parallelize something without having to pull in OpenMP or something.
They're only supported in MSVC and GCC (for the latter you need to link against Intel's TBB to make it work). Support in libc++ (Clang) is work in progress.
Clang does support parallel stl already (requires either TBB or OpenMP).
Our project https://github.com/elalish/manifold made use of this to speed up mesh processing algorithms a lot.
Yes, but actually small can often be much larger then 100-300 depending on the specifics. Programmers often vastly underestimate how fast cache, and prefetch can go compared to complicated data structures.
... Or much smaller, I remember a benchmark for a case I had a few years ago, the cutoff I had for a map being faster than std::vector/array & linear probing was closer to N=10 that 100.
(Not std::map, at the time it must have been something like tsl:: hopscotch_map).
Note also that nowadays for instance boost comes with state-of-the-art flat_map and flat_unordered_map which gives both the cache coherency for small sizes and the algorithmic characteristics of various kinds of maps
Exactly. I measured vector vs an efficient linear probing hash map very recently and the cutoff was single digit. Even against unordered_map or plain std::map the cutoff was surprisingly low (although in this case I would trust a synthetic benchmark significantly less).
Sure, the point here is with all the specific context specific details, your most likely comparing apples versus oranges. So simple complexity analysis or a general rule without benchmarks and a good understanding of the system and how it interacts with your details is not going to solve your problem.
So you're saying that if I had had to store 100 elements in the memory, I would be better off using hashmap instead of vector/array? What type of elements did you use in your experiment or how large they were and what was your access pattern?
A successful search in a vector will do, on average, 50 comparisons, while the hash map version would hash the key, look up the bucket, typically find a single-item in that bucket (with only a 100 items in the hashtag, hash collisions will be highly unlikely), and do a single comparison.
For an unsuccessful search, the vector version would do 100 key comparisons, and the hashtag would do a single hash, lookup the bucket, and almost certainly find it empty.
So, if you make the comparison function relatively expensive, I can see the hash map being faster at search.
Even relatively short string keys might be sufficient here, if the string data isn’t stored inline. Then, the key comparisons are likely to cause more cache misses than accessing a single the bucket.
Of course, the moment you start iterating over all items often, the picture will change.
Searching the vector is literally incrementing a pointer over the data. The number of instructions needed to do the search is very small - e.g. ~15. This means that it can very easily fit into the CPU uOp cache but also makes it a candidate for the LSD cache. Both of those will be a major factor in hiding the latencies or getting rid of them in the CPU frontend fetch-decode pipeline, effectively making all the for-loop iterations only left to be bound by the CPU backend, or more specifically, branch-mispredictions (aka ROB flushing) and memory latencies.
Given the predictable access nature of vectors and their contiguous layout in the memory, the CPU backend will be able to take advantage of those facts and will be able to hide the memory latency (even within the L1+L2+L3 cache) by pre-fetching the data on consecutive cache-lines just as you go through the loop. Accessing the data that resides in L1 cache is ~4 cycles.
The "non-branchiness" of such code will make it predictable and as such will make it a good use of BTB buffers. Predictability will prevent the CPU from having to flush the ROB and hence flushing the whole pipeline and starting all over again. The cost of this is one of the largest there are within the CPU and it is ~15 cycles.
OTOH searching the open-addressing hashmap is the super-set of that - e.g. almost as if you're searching over an array of vectors. So, only the search code is: (1) By several factors larger, (2) Much more branchy, (3) Less predictable and (4) Less cache-friendly.
Algorithmically speaking, yes, what you're saying makes sense, but I think the whole picture can only be made once the hardware details are also taken into account. Vector approach will literally be only bound by the number of cycles it takes to fetch the data from L1 cache and I don't see that happening for a hash-map.
I think you're missing my point. I'm highly suspicious, or let's say intrigued, under what conditions one can come up with such conclusion. Therefore I asked for a clarification.
vectors (or arrays) outperform everything else if the dataset is small. Small is usually in the order of 100-300, but can vary wildly.
This is a very poor way to choose a data structure. How many items you want to store is not what someone should be thinking about.
How you are going to access it is what is important. Looping through it - vector. Random access - hash map. These two data structures are what people need 90% of the time.
If you are putting data on the heap it is already because you don't know how many items you want to store.
Isn't that because view performs the procedure and access when the data is accessed? It's mainly meant so that you don't have to load all this memory in or stall when accessing the view, and if you don't need that capability, the regular algorithm stl is better.
iirc, on msvc, execution parallel delegates to the OS (windows) to decide how many threads to create, at it is usually more than the total number of vcpu contrary to the usual recommendation.
It's very much implementation defined yes. I'm currently using this for something that runs for about 10 seconds, and even music playback and mouse cursor movement gets affected.
I rarely meet a CS major who will accept that small things will always stay small. They will frequently talk you into more complex data structures with the assurance that you are just too stupid to realize your problem will suddenly need to scale several orders of magnitude. Do they teach you in CS-101 to interpret '+' as the exponential operator? It often feels that way.
Are they fresh graduates? It is very important to understand the workload distribution for any optimization. Even if small things can sometimes get large, optimizing for the small case can often yield large gain as they may occur frequently. And complex data structures are usually worse in the small case...
A vector should be people's default data structure, but this presentation is bizarre, because it is based on looping through every element of a vector or a list to find the element you want.
This is never a scenario that should happen, because if you are going to retrieve an arbitrary element it should be in a hash map or sorted map.
Reflections alone would be one of the most impactful additions. And in contrast to most others: very difficult to do otherwise. I'm a bit surprised by the sudden push after long phase where it seemed like they would never come.
Contacts: yes please. Variadic indexing is one of those things everyone writes their own helper for. But this standard facility is very welcome indeed.
Some additions seem a bit of of scope for the standard of a language that famously refuses to fix mistakes. So in weary about std::hive, networking, physical units.
And an underrated cherry is at the end: cleaning up those "ill formed, no diagnostic required" clauses in the standard. For those who don't know: there are things forbidden in the standard which the compiler is allowed to not tell you (because it's difficult for the compiler to prove it). In particular this is omnipresent in the constexpr world. Leading to silly redundant code that manually assets things to explicitly trigger the compiler to check for errors.
Apparently someone showed up to pick up the work regarding reflection.
However at least we already have a kind of poor man's reflection, with constexpr if + concepts + type traits.
As for the rest, I am also not a big fan, but until my favourite language runtimes and GPGPU tools switch to something else, C++ is part of the toolbox. No need to add even more layers.
Reflection will be a welcome addition whenever it arrives. On the other hand, whatever is standardize will be a profound disappointment compared to Circle C++.
boost::pfr is also huge for reflection in C++. It leverages corner cases of the language and compilers but does so uniformly (works for MSVC, GCC, clang which is all that matters in 2023).
I've never read a programming book that was worth it. In the time and the energy it takes to read, I could have always learned more by reading a tldr and trying things myself
Not OP, but I agree with the sentiment. To me, it seemed like for a long time, people accepted whatever Martin said as “the right way” without much thought. He has had many good ideas, but also some bad ones. “Clean Code” hasn’t aged well, for example. There are a bunch of good ideas in it that happily have become commonplace (and so don’t require a the book anymore), but many bad ones too. Usually the book was recommended without qualification.
And personally, I always chafed at the “Uncle Bob” moniker. I’m a grown-ass man, and I’m not calling some random guy “Uncle Bob” unless he’s related to me. Calling yourself “Uncle Bob” seems creepy, and it makes me feel like I’m supposed to look up to him by default. No. I’d rather look to people like Rich Hickey or John Ousterhout, who have no similar pretensions. They’re just experienced practitioners sharing what they’ve learned.
Is unit test driven development fundamentalism politics?
His attitude towards development has always been way too dogmatic with not nearly enough focus on trade offs. It's probably not a coincidence that his politics trend that way too but it doesn't affect how good or bad his advice is.
For some reason, the comparison is always current rust Vs 20 year old c++. Mentioning that "modern" (12 year old) c++ does not have these problems gets downvoted.
Completely unrelated: there are at least two dedicated anti c++ communities.
> Mentioning that "modern" (12 year old) c++ does not have these problems gets downvoted.
Because it's false, that's why. Modern C++ still has many/most of C++ problems. It solves a bunch of them, but far from all.
And telling the opposite to newcomers is a lie that's hurting them because they can end up making even more mistakes than the previous generation, since they were told they didn't have to pay attention thanks to “modern C++”.
> Mentioning that "modern" (12 year old) c++ does not have these problems gets downvoted.
I'm not a C++ user but I thought that all of these things are still in "modern" C++, that the new editions only add things, not remove? Are there tools that can automatically rewrite existing code to use the "modern" features?
And that's a criticism I can take to a degree on behalf of the language. These relics are still in because mistakes are happening in the governing body. However in practice, they don't matter much. Every CPP dev has a little helper running in the background which immediately flags these mistakes and can auto correct them. It's not an issue, just an annoyance.
This doesn't fly with a one man team and not with a 1000. It's just badly done, there's no sugarcoating. Those meshes should never end up in the game files.
>This doesn't fly with a one man team and not with a 1000
sounds like someone never worked on a 1000 dev team. random quirks either go unnoticed or are de-prioritized all the time. Most are minor, more and more moderate to major ones are getting through. That's definitely a publisher issue.
random quirks do. this is not random quirks. it's a systematic and expected issue of underoptimisation caused by releasing a product before it was even slated to be ready. one bad mesh is not the issue, it's never the issue. we're talking of thousands of terrible meshes and a near-total lack of basic optimisations applied at the last stage of development to most games. the manpower was not enough to release within the deadline, likely due to running into a lot of technical difficulties working with unity. instead of going into valve time, they released it anyway, which means that you skipped the entire polish and optimisation part not only for the game itself but for half the engine as well. poor performance was not only expected, i'm certain that every member of the team saw it as the only possible outcome.
I'd call 4 examples of "this needed LODs" random quirks in the grand scheme of things. It's not like every single mesh is 100k vertices. Grossly underoptimized, yes. But the devs pre-empting their announcement with "we're not satisfied" tells me they were too busy slaying dragons to worry about the annoying barking Chihuahua in the room.
It was expected, yes. It does not mean they weren't trying to fix it in the 11th hour. I woildnt be surprised if some core tech was unfinished or inadequate that lead to this.
>instead of going into valve time, they released it anyway, which means that you skipped the entire polish and optimisation part not only for the game itself but for half the engine as well.
Yup, welcome to game development when you have deadlines and no benevolent (or at least, apathetic) dictator paying your bills. It's unfortunate that we can trace this back to the 80's with ET, but this is simply the business realities. Game code isn't mission critical (and until recently, does not care about maintainability), and also isn't what sells the product.
So it never gets the time to be cultivated like other indistries. And people still buy anyway. It's a two way street of apathy and every publisher hopes it can slip under the cracks and not become the next Superman 64. Most manage to slip.
There's not much you can do about it with the current publishing structure, where most funders don't work in nor care about games. And the ones that do still see their money draining whenever the talk of delays come up. That won't be solved except with time as more industry trailblazers retire and shift to management (remember, Todd Howard is only in his 50's. Gabe and Kojima are 60. So many pioneers are still well under retirement age). Or for more truly indie teams to arise and learn how to scale up projects while staying lean. The latter is what I hope to do.
It's pretty clear that with the performance that the game has it's a lot more than four models with bad LODs. They would probably have identified that issue within days. There's likely a more fundamental issue, not only with the technology but also with LODs for most detail models. These are only examples since you can't list every model out of hundreds being rendered.
I really think that the performance and scale indie developers can squeeze out puts AAA developers to shame nowadays, and I really hope that that'll continue to happen. All it takes is time, organisation, and a lot of time.
Sure, more than 4, less than however many assets there are in the game. I mostly want to emphasize that a systematic issue implies that this was an acceptable development pipeline, which I doubt any engineer on the team would say.
>I really think that the performance and scale indie developers can squeeze out puts AAA developers to shame nowadays, and I really hope that that'll continue to happen. All it takes is time, organisation, and a lot of time.
Yup, I agree. Indies don't tend to have money, so the budget comes from. Elsewhere. We can already utilize some amazing tools to cut down the time of scaling up environments. Not as much with actor assets. But I don't think it's too far off (more just locked off in acedemics white papers).
The systematic issue refers to the fact that it is both prevalent and a result of the early release, more a systematic issue of modern AAA development studio organisation than a development practice by developers.
