ZhaoKang via llvm-dev
2016-Jul-25 07:19 UTC
[llvm-dev] How to use map/set in LLVM to disable automatic sorting?
Hello LLVM, We found that many LLVM passes use map/set containers to increase the searching efficiency. Although map/set has automatic sorting feature, the results after the same pass transformation are still the same. If native map/set, we think the order after inserting new element may change. So, my question is, does LLVM use its own-defined structure instead of native map/set? Or, LLVM disables such feature for map/set? Could you give a detailed explanation? Thanks! Kang -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160725/f4748c0a/attachment.html>
Jonathan Roelofs via llvm-dev
2016-Jul-25 18:15 UTC
[llvm-dev] How to use map/set in LLVM to disable automatic sorting?
On 7/25/16 1:19 AM, ZhaoKang via llvm-dev wrote:> Hello LLVM, > > > We found that many LLVM passes use map/set containers to increase the > searching efficiency. > > Although map/set has automatic sorting feature, the results after the > same pass transformation are still the same. > > If native map/set, we think the order after inserting new element may > change. > > So, my question is, does LLVM use its own-defined structure instead of > native map/set?Yes, in places where iteration order matters, we try really hard to use ADT's that have a deterministic iteration order, so that the passes themselves remain deterministic. See: http://llvm.org/docs/ProgrammersManual.html#picking-the-right-data-structure-for-a-task Jon> Or, LLVM disables such feature for map/set? > > Could you give a detailed explanation? > > Thanks! > > > > Kang > > > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-- Jon Roelofs jonathan at codesourcery.com CodeSourcery / Mentor Embedded
Mehdi Amini via llvm-dev
2016-Jul-25 20:23 UTC
[llvm-dev] How to use map/set in LLVM to disable automatic sorting?
> On Jul 25, 2016, at 12:19 AM, ZhaoKang via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hello LLVM, > > > > We found that many LLVM passes use map/set containers to increase the searching efficiency. > > Although map/set has automatic sorting feature, the results after the same pass transformation are still the same. > > If native map/set, we think the order after inserting new element may change. > > So, my question is, does LLVM use its own-defined structure instead of native map/set? Or, LLVM disables such feature for map/set? >I don’t really understand the question, can you provide an example of passes and what problem do you expect? — Mehdi> Could you give a detailed explanation? > > Thanks! > > > Kang > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160725/0559caca/attachment.html>
Jonathan Roelofs via llvm-dev
2016-Jul-28 13:53 UTC
[llvm-dev] How to use map/set in LLVM to disable automatic sorting?
On 7/27/16 8:54 PM, ZhaoKang wrote:> Jon, > > Thanks a lot for your reply! > We will look the detailed implementation in LLVM. > In my opinion, it seems that SetVector class just defines such type, which is has the same efficiency with set, but stays a stable order.Time-efficiency for set lookup should be the same. Space-efficiency on the other hand is lost because the addition of the vector storage needed for the stable iteration order. Jon> > Kang > > >> -----原始邮件----- >> 发件人: "Jonathan Roelofs" <jonathan at codesourcery.com> >> 发送时间: 2016-07-26 02:15:17 (星期二) >> 收件人: ZhaoKang <zhaokang at mail.tsinghua.edu.cn>, llvm-dev at lists.llvm.org >> 抄送: >> 主题: Re: [llvm-dev] How to use map/set in LLVM to disable automatic sorting? >> >> >> >> On 7/25/16 1:19 AM, ZhaoKang via llvm-dev wrote: >>> Hello LLVM, >>> >>> >>> We found that many LLVM passes use map/set containers to increase the >>> searching efficiency. >>> >>> Although map/set has automatic sorting feature, the results after the >>> same pass transformation are still the same. >>> >>> If native map/set, we think the order after inserting new element may >>> change. >>> >>> So, my question is, does LLVM use its own-defined structure instead of >>> native map/set? >> >> Yes, in places where iteration order matters, we try really hard to use >> ADT's that have a deterministic iteration order, so that the passes >> themselves remain deterministic. >> >> See: >> http://llvm.org/docs/ProgrammersManual.html#picking-the-right-data-structure-for-a-task >> >> >> Jon >> >>> Or, LLVM disables such feature for map/set? >>> >>> Could you give a detailed explanation? >>> >>> Thanks! >>> >>> >>> >>> Kang >>> >>> >>> >>> >>> >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >> >> -- >> Jon Roelofs >> jonathan at codesourcery.com >> CodeSourcery / Mentor Embedded > > > >-- Jon Roelofs jonathan at codesourcery.com CodeSourcery / Mentor Embedded