[llvm-dev] How to use map/set in LLVM to disable automatic sorting?

[Jonathan Roelofs via llvm-dev]

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