On Jan 20, 2013, at 7:46 AM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:>> It is one of the motivations. > > The reason I ask is that STL comes all ready, with containers and algorithms. They may not be optimal for every task, but they do their job and they are part of the standard. There may be some price to pay in terms of performance/memory usage/etc. for a specific application, but overall it may be worth it. Evidently, in case of LLVM, someone (you?) decided that having local set of containers is a better idea. I simply want to understand the reasons behind this decision.I'm confused here. You're acting as though we don't use the STL. In fact, we do use std::string, std::vector, std::map etc when they are the right solution for the job. We are not avoiding the STL, we're just not using it when it isn't the best tool for a job. LLVM's purpose isn't to use inappropriate C++ containers just because they are "standard". Our goal is to build the best compiler possible, and if that means we have to implement custom containers, so be it. I would really like for the C++ standard library to provide containers better than what LLVM does, but until it does, we are stuck with ours.> I quickly looked over the library section on containers in the C++03 standard and I didn't see any paragraphs regarding the allocation strategy for classes like "set" or "map". The LLVM page seems to contain information that was based on some specific implementation (or several implementations), but was not mandated by the standard itself.We live in a pragmatic world, not a theoretical one. -Chris
On 1/21/2013 12:35 AM, Chris Lattner wrote:> > I'm confused here. You're acting as though we don't use the STL. In fact, we do use std::string, std::vector, std::map etc when they are the right solution for the job.I'm trying to understand the reasoning behind the decisions made at the beginning of LLVM. My working assumption is that ADT didn't exist when LLVM started (whereas STL did). In such case, I'm assuming that creation of ADT was motivated by needs of LLVM that STL didn't meet. I'm trying to understand what the needs were and where STL was considered inadequate. Creating a new set of containers is an investment, so, again, I'm assuming that there were specific motives that caused that investment to be made. Benjamin's answer was actually very informative, that was that kind of information I was looking for. -Krzysztof -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
It also provides a level of consistency. Different systems/compilers can use different STL implementations with different characteristics. The LLVM containers are a known quantity when trying to assess performance. On Mon, Jan 21, 2013 at 8:08 AM, Krzysztof Parzyszek < kparzysz at codeaurora.org> wrote:> On 1/21/2013 12:35 AM, Chris Lattner wrote: > >> >> I'm confused here. You're acting as though we don't use the STL. In >> fact, we do use std::string, std::vector, std::map etc when they are the >> right solution for the job. >> > > I'm trying to understand the reasoning behind the decisions made at the > beginning of LLVM. My working assumption is that ADT didn't exist when > LLVM started (whereas STL did). In such case, I'm assuming that creation > of ADT was motivated by needs of LLVM that STL didn't meet. I'm trying to > understand what the needs were and where STL was considered inadequate. > Creating a new set of containers is an investment, so, again, I'm assuming > that there were specific motives that caused that investment to be made. > Benjamin's answer was actually very informative, that was that kind of > information I was looking for. > > > -Krzysztof > > -- > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted > by The Linux Foundation > ______________________________**_________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/**mailman/listinfo/llvmdev<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev> >-- Thanks, Justin Holewinski -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130121/8dda3f20/attachment.html>
On Mon, Jan 21, 2013 at 3:08 PM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:> On 1/21/2013 12:35 AM, Chris Lattner wrote: >> I'm confused here. You're acting as though we don't use the STL. In >> fact, we do use std::string, std::vector, std::map etc when they are the >> right solution for the job. > > I'm trying to understand the reasoning behind the decisions made at the > beginning of LLVM. My working assumption is that ADT didn't exist when LLVM > started (whereas STL did). In such case, I'm assuming that creation of ADT > was motivated by needs of LLVM that STL didn't meet. I'm trying to > understand what the needs were and where STL was considered inadequate. > Creating a new set of containers is an investment, so, again, I'm assuming > that there were specific motives that caused that investment to be made. > Benjamin's answer was actually very informative, that was that kind of > information I was looking for.Also, there was no hashtable in STL before C++11 (DenseMap), and there is still no StringRef and ArrayRef equivalent. Dmitri -- main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/
On Mon, Jan 21, 2013 at 8:08 AM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:> On 1/21/2013 12:35 AM, Chris Lattner wrote: >> >> >> I'm confused here. You're acting as though we don't use the STL. In >> fact, we do use std::string, std::vector, std::map etc when they are the >> right solution for the job. > > > I'm trying to understand the reasoning behind the decisions made at the > beginning of LLVM. My working assumption is that ADT didn't exist when LLVM > started (whereas STL did). In such case, I'm assuming that creation of ADT > was motivated by needs of LLVM that STL didn't meet. I'm trying to > understand what the needs were and where STL was considered inadequate. > Creating a new set of containers is an investment, so, again, I'm assuming > that there were specific motives that caused that investment to be made.> Benjamin's answer was actually very informative, that was that kind of > information I was looking for.You can actually see what happened if you look back far enough in the mailing list: One common idiom was: Someone saw that X and Y optimization passes were slow They determined the slowness was in the containers The containers turned out to be slow on all platforms New containers were implemented They made real world significant differences in speed on all platforms The new containers were used. The alternative would have been to try to get patches into multiple STL's, and then tell everyone in the world to upgrade. IE "Oh, LLVM is slow if you are on GCC 4.3.6, you need 4.3.7, or MSVC 2012, or XLC 11.9 or ...". Every so often someone determines some optimization pass is still using XX percent of time in a container, they test various containers, discover that either it's faster or slower than other alternatives, and LLVM adjusts accordingly.
On Jan 21, 2013, at 5:08 AM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:> On 1/21/2013 12:35 AM, Chris Lattner wrote: >> >> I'm confused here. You're acting as though we don't use the STL. In fact, we do use std::string, std::vector, std::map etc when they are the right solution for the job. > > I'm trying to understand the reasoning behind the decisions made at the beginning of LLVM. My working assumption is that ADT didn't exist when LLVM started (whereas STL did).Right. LLVM started using the stl much more pervasively. When I (and others) started using an actual profiler on it (2006 or later?) ADT started coming into existence.> In such case, I'm assuming that creation of ADT was motivated by needs of LLVM that STL didn't meet. I'm trying to understand what the needs were and where STL was considered inadequate. Creating a new set of containers is an investment, so, again, I'm assuming that there were specific motives that caused that investment to be made. Benjamin's answer was actually very informative, that was that kind of information I was looking for.As DannyB says, the best way to find this is svn history. Look at and near the commits that added SmallVector.h or whatever. -Chris