On Jan 19, 2013, at 7:04 PM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:> On 1/19/2013 8:36 PM, Chris Lattner wrote: >> >> See: >> http://llvm.org/docs/ProgrammersManual.html#picking-the-right-data-structure-for-a-task > > Were the "small n" characteristics the main motivation?It is one of the motivations.> Memory-wise, STL classes allow user-defined allocators, so use of things like memory pools should be relatively straightforward. Just wondering... :)Yes, you get some of the benefits that way, but not all of it. -Chris
On 1/19/2013 10:00 PM, Chris Lattner wrote:> On Jan 19, 2013, at 7:04 PM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote: >> >> Were the "small n" characteristics the main motivation? > > It is one of the motivations.What were the others? 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 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. -Krzysztof -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
On 20.01.2013, at 16:46, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:> On 1/19/2013 10:00 PM, Chris Lattner wrote: >> On Jan 19, 2013, at 7:04 PM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote: >>> >>> Were the "small n" characteristics the main motivation? >> >> It is one of the motivations. > > What were the others? > > 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 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.The containers in the STL are general purpose classes that are fast for a wide variety of different elements but don't excel on any special case. The LLVM classes are much more specialized. For example DenseMap is a hash table that embeds both keys and values into a big table of memory. This gives nice cache behavior for simple pointer-to-pointer mappings which are common throughout LLVM while std::map wastes memory and has worse cache behavior. For big keys DenseMap wastes a ton of memory and becomes slow, std::map is better for those cases. Another example: clang's lexing speed is directly bound by StringMap, a specialized hash table for string keys (std::map<std::string, …> is extremely slow in comparison). A fast lexer is a big deal when you want to embed clang into an IDE and still get responsive autocompletion. Most of the containers in LLVM were motivated by cases where the standard containers were just too slow and needed a replacement. Some of them were closely related to a bad implementation decision in a particular version of the standard library, e.g. libstdc++'s std::string doesn't implement the small string optimization, making incremental building of strings slow, to make that use case faster SmallString was invented. Now that small std::strings are more commonly implemented we may want to retire it eventually. - Ben
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 Sun, Jan 20, 2013 at 7:46 AM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:> On 1/19/2013 10:00 PM, Chris Lattner wrote: >> >> On Jan 19, 2013, at 7:04 PM, Krzysztof Parzyszek <kparzysz at codeaurora.org> >> wrote: >>> >>> >>> Were the "small n" characteristics the main motivation? >> >> >> It is one of the motivations. > > > What were the others? > > 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 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.+1 to Chris's answers, and this is somewhat off topic for this list, but to answer this paragraph: C++03 and C++11 don't explicitly specify the allocation strategy for set or map (or unordered_map), but they do specify when iterators and pointers can be invalidated, which only allows one or a few allocation strategies. Jeffrey
We should not blinding worship STL. It might be general purpose but it can be a big performance drain in memory and/or runtime. I really like the StringRef class for example. -----Original Message----- From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Krzysztof Parzyszek Sent: Sunday, January 20, 2013 7:46 AM To: Chris Lattner Cc: llvmdev at cs.uiuc.edu Subject: Re: [LLVMdev] std::string On 1/19/2013 10:00 PM, Chris Lattner wrote:> On Jan 19, 2013, at 7:04 PM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote: >> >> Were the "small n" characteristics the main motivation? > > It is one of the motivations.What were the others? 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 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. -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