llvm dev - Jul 2019 - Using bytecode version of std::sort for JIT generated data type

Thanks David! I understand that std::sort doesn't exist without types
especially at bytecode layer.

What I was thinking was something like the following:

Compile std::sort with a thunk function Compare(void*, void*) {rerturn
false} into bytecode with an option say noinline and always make the
function call or even a simple unoptimized bytecode which guarantees that
Compare exists as a function without any inlining.

At run time implement a new Compare function for your type and replace the
Compare function with the new Compare implemented with JIT. Now the JIT
runtime has whole program in bytecode which it can aggressively optimize.
A good way to realize this "thunking" into LLVM JIT can enable lots of
optimized algorithms to be ported into JIT without having to re-invent them
for each JIT runtime.

Thoughts?

On Wed, Jul 3, 2019 at 3:56 PM David Blaikie <dblaikie at gmail.com>
wrote:
> If you consider how std::sort works - it doesn't exist in the machine
(or
> even LLVM IR) level without a specific type - so if you were to support
> something like std::sort in your language (JITed or not), it means some
> form of specialization of your types/functions based on other types.
>
> So, yes, something like "own Sort function inside JIT" - if your
language
> doesn't support a way to write this in the language itself (if it
doesn't
> have anything like C++ templates or an equivalent generic thing).
>
> Otherwise you can do something like qsort (which uses a function pointer
> to parameterize the comparison) & perhaps force or encourage the
optimizer
> to inline and collapse away this indirection.
>
> On Wed, Jul 3, 2019 at 3:43 PM Rajesh S R via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi LLVM devs,
>> The performance of C++ std::sort comes from being able to inline the
>> comparator. For a JIT generated data type, using the comparator as a
>> function call from std::sort may not be ideal. So, i was wondering how
can
>> we make a JIT-sort which is as good as statically compiled std::sort
with
>> comparator inlined.
>>
>> What is the recommended way to pass a an existing function like
std::sort
>> into JIT so that it can optimize the whole program? For example, how do
we
>> generate the bytecode for existing function (say some external tools)
and
>> give to JIT runtime. Is there some code sample?
>>
>> The alternative is to rollout my own Sort function inside JIT, but i
>> don't want to do that and want to take this as an opportunity to
learn the
>> general approach of passing existing function definitions into JIT to
do
>> whole program optimization like inlining.
>>
>> I found this stackoverflow question
>>
<https://stackoverflow.com/questions/10587250/fast-to-compile-efficient-sort-algorithm-for-jit-compilation>which
>> is related to what I am asking for, but I don't see any final
conclusion on
>> this beyond incurring a function call for each comparison.
>>
>> Thanks!
>>
>> Rajesh S R
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://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/20190703/4ea81ac9/attachment.html>

That's an option, for sure - having llvm::Functions you could clone into
your module, replace the call to the Compare function to a call to the
specific comparison you want & the let the optimizers do their work.

On Wed, Jul 3, 2019 at 4:23 PM Rajesh S R <srrajesh1989 at gmail.com>
wrote:
> Thanks David! I understand that std::sort doesn't exist without types
> especially at bytecode layer.
>
> What I was thinking was something like the following:
>
> Compile std::sort with a thunk function Compare(void*, void*) {rerturn
> false} into bytecode with an option say noinline and always make the
> function call or even a simple unoptimized bytecode which guarantees that
> Compare exists as a function without any inlining.
>
> At run time implement a new Compare function for your type and replace the
> Compare function with the new Compare implemented with JIT. Now the JIT
> runtime has whole program in bytecode which it can aggressively optimize.
> A good way to realize this "thunking" into LLVM JIT can enable
lots of
> optimized algorithms to be ported into JIT without having to re-invent them
> for each JIT runtime.
>
> Thoughts?
>
> On Wed, Jul 3, 2019 at 3:56 PM David Blaikie <dblaikie at gmail.com>
wrote:
>
>> If you consider how std::sort works - it doesn't exist in the
machine (or
>> even LLVM IR) level without a specific type - so if you were to support
>> something like std::sort in your language (JITed or not), it means some
>> form of specialization of your types/functions based on other types.
>>
>> So, yes, something like "own Sort function inside JIT" - if
your language
>> doesn't support a way to write this in the language itself (if it
doesn't
>> have anything like C++ templates or an equivalent generic thing).
>>
>> Otherwise you can do something like qsort (which uses a function
pointer
>> to parameterize the comparison) & perhaps force or encourage the
optimizer
>> to inline and collapse away this indirection.
>>
>> On Wed, Jul 3, 2019 at 3:43 PM Rajesh S R via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> Hi LLVM devs,
>>> The performance of C++ std::sort comes from being able to inline
the
>>> comparator. For a JIT generated data type, using the comparator as
a
>>> function call from std::sort may not be ideal. So, i was wondering
how can
>>> we make a JIT-sort which is as good as statically compiled
std::sort with
>>> comparator inlined.
>>>
>>> What is the recommended way to pass a an existing function like
>>> std::sort into JIT so that it can optimize the whole program? For
example,
>>> how do we generate the bytecode for existing function (say some
external
>>> tools) and give to JIT runtime. Is there some code sample?
>>>
>>> The alternative is to rollout my own Sort function inside JIT, but
i
>>> don't want to do that and want to take this as an opportunity
to learn the
>>> general approach of passing existing function definitions into JIT
to do
>>> whole program optimization like inlining.
>>>
>>> I found this stackoverflow question
>>>
<https://stackoverflow.com/questions/10587250/fast-to-compile-efficient-sort-algorithm-for-jit-compilation>which
>>> is related to what I am asking for, but I don't see any final
conclusion on
>>> this beyond incurring a function call for each comparison.
>>>
>>> Thanks!
>>>
>>> Rajesh S R
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> https://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/20190708/3e71a321/attachment.html>

Thanks David!

I am not clear on how to achieve this though. Could you give more info on
this?

I expect something like this:

sort.cc file:

bool Compare(void* a, void* b) {
  return false;
}

void SortFunc(void* arr, int len) {
   std::sort(arr, len, &Compare)
}

$MAGIC_COMMAND sort.cc -o a.llvm

a.llvm is a bytecode which can be loaded at runtime in my JIT module and
write some code to replace "Compare" function with our own
"Compare"
function.



On Mon, Jul 8, 2019 at 1:17 PM David Blaikie <dblaikie at gmail.com>
wrote:
> That's an option, for sure - having llvm::Functions you could clone
into
> your module, replace the call to the Compare function to a call to the
> specific comparison you want & the let the optimizers do their work.
>
> On Wed, Jul 3, 2019 at 4:23 PM Rajesh S R <srrajesh1989 at gmail.com>
wrote:
>
>> Thanks David! I understand that std::sort doesn't exist without
types
>> especially at bytecode layer.
>>
>> What I was thinking was something like the following:
>>
>> Compile std::sort with a thunk function Compare(void*, void*) {rerturn
>> false} into bytecode with an option say noinline and always make the
>> function call or even a simple unoptimized bytecode which guarantees
that
>> Compare exists as a function without any inlining.
>>
>> At run time implement a new Compare function for your type and replace
>> the Compare function with the new Compare implemented with JIT. Now the
JIT
>> runtime has whole program in bytecode which it can aggressively
optimize.
>> A good way to realize this "thunking" into LLVM JIT can
enable lots of
>> optimized algorithms to be ported into JIT without having to re-invent
them
>> for each JIT runtime.
>>
>> Thoughts?
>>
>> On Wed, Jul 3, 2019 at 3:56 PM David Blaikie <dblaikie at
gmail.com> wrote:
>>
>>> If you consider how std::sort works - it doesn't exist in the
machine
>>> (or even LLVM IR) level without a specific type - so if you were to
support
>>> something like std::sort in your language (JITed or not), it means
some
>>> form of specialization of your types/functions based on other
types.
>>>
>>> So, yes, something like "own Sort function inside JIT" -
if your
>>> language doesn't support a way to write this in the language
itself (if it
>>> doesn't have anything like C++ templates or an equivalent
generic thing).
>>>
>>> Otherwise you can do something like qsort (which uses a function
pointer
>>> to parameterize the comparison) & perhaps force or encourage
the optimizer
>>> to inline and collapse away this indirection.
>>>
>>> On Wed, Jul 3, 2019 at 3:43 PM Rajesh S R via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>>> Hi LLVM devs,
>>>> The performance of C++ std::sort comes from being able to
inline the
>>>> comparator. For a JIT generated data type, using the comparator
as a
>>>> function call from std::sort may not be ideal. So, i was
wondering how can
>>>> we make a JIT-sort which is as good as statically compiled
std::sort with
>>>> comparator inlined.
>>>>
>>>> What is the recommended way to pass a an existing function like
>>>> std::sort into JIT so that it can optimize the whole program?
For example,
>>>> how do we generate the bytecode for existing function (say some
external
>>>> tools) and give to JIT runtime. Is there some code sample?
>>>>
>>>> The alternative is to rollout my own Sort function inside JIT,
but i
>>>> don't want to do that and want to take this as an
opportunity to learn the
>>>> general approach of passing existing function definitions into
JIT to do
>>>> whole program optimization like inlining.
>>>>
>>>> I found this stackoverflow question
>>>>
<https://stackoverflow.com/questions/10587250/fast-to-compile-efficient-sort-algorithm-for-jit-compilation>which
>>>> is related to what I am asking for, but I don't see any
final conclusion on
>>>> this beyond incurring a function call for each comparison.
>>>>
>>>> Thanks!
>>>>
>>>> Rajesh S R
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> https://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/20190708/90577204/attachment.html>