llvm dev - Jul 2016 - 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>

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

> 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>

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