Pull to refresh

Простой тест libjit vs llvm

Reading time 20 min
Views 2.1K
«И опыт, сын ошибок трудных» (с) Сами знаете кто

С самого детства меня интересовали вопросы типа "кто победит — слон или кит". Или, например, "кто сильнее — тигр или лев". Теперь, когда я стал взрослым, вопросы немного изменились. Теперь меня интересует в частности — что круче libjit или llvm.

Понятно, что простым способом на такой вопрос не ответить, это продукты у которых экологические ниши не полностью совпадают, однако всегда можно написать простой тест и посмотреть — насколько приятно было писать, насколько быстро выполняется результат, и по крайней мере, составить впечатления о продуктах не из хвалебных статей а, так сказать, личным опытом.

Итак. Простая задача — решето Эратосфена, или поиск простых чисел.



За основы я взял ту реализацию, которая указана в Википедии, к этому я добавил цикл для запуска сита эратосфена много раз. Получилось так:

001:  program erato;
002:  
003:  procedure eratosphen (n :integer);
004:  var
005:    a: array[0..100000of byte;
006:    q: integer;
007:    i,j:integer;
008:  begin
009:  FillChar(a,sizeof(a),1);
010:  q:=round(sqrt(n));
011:  for i:=2 to q do
012:   if a[i]=1 then
013:     begin
014:       j:=i*i;
015:       while j<=do
016:         begin
017:           a[j]:=0;
018:           j:=j+i;
019:         end;
020:    end;
021:  end;
022:  
023:  var i:integer;
024:  begin
025:   Writeln('Poexali');
026:   for i:=1 to 5000 do
027:        eratosphen(100000);
028:  end.
029:  


LIBJIT вариант


При использовании libjit получилась такая программа:

001#include <stdio.h>
002: #include <jit/jit.h>
003: 

004: unsigned int myprintunsigned int a) {
005:   printf(" %d\n",a);
006: }
007: 
008: jit_function_t main_function, erato;
009: 
010: 
011: void create_erato()
012: {
013:   jit_type_t params[1];
014:   jit_type_t signature;
015:   jit_label_t for_begin = jit_label_undefined;
016:   jit_label_t end_for = jit_label_undefined;
017:   jit_label_t end_if = jit_label_undefined;
018:   jit_label_t while_end = jit_label_undefined;
019:   jit_label_t while_begin = jit_label_undefined;
020:   jit_label_t print_end = jit_label_undefined;
021:   jit_label_t print_begin = jit_label_undefined;
022:   jit_label_t print_if = jit_label_undefined;
023:   void *args[2];
024:   jit_uint result;
025:   jit_value_t n,a,one1,szero,uint1,two2;
026:   jit_int arg1;
027:   jit_intrinsic_descr_t tofloat = {jit_type_nfloat,NULL, jit_type_uint,NULL};
028:   jit_intrinsic_descr_t toint = {jit_type_uint,NULL, jit_type_nfloat,NULL};
029:   jit_value_t temp1,temp2,q;
030:   jit_value_t i,j,elem;
031:   jit_value_t for_cond, if_cond, while_cond, print_cond;
032:   jit_value_t tmpi, tmp3,tmp4;
033:   /* Create a context to hold the JIT's primary state */
034:   /* Build the erato signature */
035:   params[0= jit_type_uint;
036:   signature = jit_type_create_signature (jit_abi_cdecl, jit_type_uint, params, 11);
037:   
038:   /* allocate sieve storage and init it by 1 */
039:   n = jit_value_get_param(erato, 0);
040:   
041:   //jit_insn_call_native(erato, "print", myprint, signature, &n ,1,0);
042: 
  a = jit_insn_alloca(erato,n);
043:   one1 = jit_value_create_nint_constant(erato, jit_type_ubyte,1);
044:   szero = jit_value_create_nint_constant(erato,jit_type_ubyte,0);
045:   jit_insn_memset(erato,a, one1,n);
046:   /* convert to float, sqrt and convert to int back */
047:   temp1 = jit_insn_call_intrinsic(erato,"convert_to_float", jit_uint_to_nfloat,&tofloat ,n, NULL);
048:   temp2 =  jit_insn_sqrt(erato, temp1);
049:   q = jit_insn_call_intrinsic(erato,"convert_to_int",jit_nfloat_to_uint,&toint ,temp2,NULL);
050:   
051:   /* for i = 2 to q do*/
052:   two2 = jit_value_create_nint_constant(erato,jit_type_uint,2);
053:   i = jit_value_create(erato,jit_type_uint);
054:   jit_insn_store(erato,i,two2);
055:   jit_insn_label(erato,&for_begin);
056:   for_cond = jit_insn_gt(erato, i, q);
057:   jit_insn_branch_if(erato,for_cond, &end_for);
058:   
059:   // if
060: 
  elem = jit_insn_load_elem(erato, a, i, jit_type_ubyte);
061:   if_cond = jit_insn_eq(erato, elem, one1);
062:   jit_insn_branch_if_not(erato,if_cond, &end_if);
063:   
064:   // j = i*i
065: 
  j=jit_value_create(erato, jit_type_uint);
066:   tmp3 = jit_insn_mul(erato, i, i);
067:   jit_insn_store(erato,j, tmp3);
068:   
069:   // while
070: 
  jit_insn_label(erato, &while_begin);
071:   while_cond = jit_insn_gt(erato,j,n);
072:   jit_insn_branch_if(erato, while_cond, &while_end);
073:   
074:   jit_insn_store_elem(erato,a,j,szero);
075:   
076:   tmp4 = jit_insn_add(erato,j,i);
077:   jit_insn_store(erato,j,tmp4);
078:   //while end
079: 
  jit_insn_branch(erato, &while_begin);
080:   jit_insn_label(erato, &while_end);
081:   // end if
082: 
  jit_insn_label(erato, &end_if);
083:   
084:   //  end for i=2 to q
085: 
  uint1 = jit_value_create_nint_constant(erato,jit_type_uint,1);
086:   tmpi = jit_insn_add(erato,i,uint1);
087:   jit_insn_store(erato,i,tmpi);
088:   jit_insn_branch(erato,&for_begin);
089:   jit_insn_label(erato, &end_for);
090:   
091:   jit_insn_return(erato, i);
092:   
093:   /* Compile the erato */
094:   jit_dump_function(stderr, erato, "erato");   
095: 
096:   jit_function_compile(erato);
097: }
098: 
099: 
100: void create_main()
101: {
102:   jit_label_t for_begin = jit_label_undefined;
103:   jit_label_t end_for = jit_label_undefined;
104:   jit_value_t temp_args[1];
105:   jit_value_t temp3,tmpi,one,n,the_i,for_cond,alot,place_for_i;
106:   jit_type_t params[2];
107:   jit_type_t signature;
108:   
109:   n = jit_value_get_param(main_function, 0);
110:   alot =  jit_value_get_param(main_function, 1);
111:   
112:    one = jit_value_create_nint_constant(main_function,jit_type_int,1);
113:    the_i = jit_value_create(main_function,jit_type_uint);
114:   
115:    place_for_i = jit_insn_alloca(main_function, jit_value_create_nint_constant(main_function,jit_type_int,4) );
116:   
117:    jit_insn_store(main_function,place_for_i,one);
118:   
119:   jit_insn_label(main_function,&for_begin);
120:   the_i = jit_insn_load(main_function,place_for_i);
121:   
122:   for_cond = jit_insn_gt(main_function, the_i, n);
123:   jit_insn_branch_if(main_function,for_cond, &end_for);
124:   
125:   temp_args[0= alot;
126:   tmpi = jit_insn_call (main_function, "erato", erato, NULL, temp_args, 1, JIT_CALL_NOTHROW);
127:   
128:   temp3 = jit_insn_add(main_function,the_i,one);
129:   
130:   jit_insn_store(main_function,place_for_i,temp3);
131:   
132:   jit_insn_branch(main_function,&for_begin);
133:   jit_insn_label(main_function, &end_for);
134:   
135:   jit_insn_return(main_function, alot);
136:   
137:   jit_dump_function(stderr, main_function, "main");   
138:   jit_function_compile(main_function);
139: //  jit_dump_function(stderr, main_function, "main_compiled");   
140: 
  
141: }
142: 
143: int main(int argc, char **argv)
144: {
145:   jit_context_t context;
146:   void *args[2];
147:   jit_uint result;
148:   jit_int arg1,arg2;
149:   jit_type_t params[2];
150:   jit_type_t signature,sign1;
151:   
152:   context = jit_context_create();
153:   
154:   /* Lock the context while we build and compile the function */
155:   jit_context_build_start(context);
156:   
157:   /* Build the function signature */
158:   params[0= jit_type_int;
159:   signature = jit_type_create_signature  (jit_abi_cdecl, jit_type_int, params, 11);
160: 
161:   erato =  jit_function_create(context, signature);
162:   create_erato();
163:   
164:   params[0= jit_type_int;
165:   params[1= jit_type_int;
166:   signature = jit_type_create_signature  (jit_abi_cdecl, jit_type_int, params, 21);
167:   
168:   main_function = jit_function_create(context, signature);
169:   create_main();
170:   
171:   /* Unlock the context */
172:   jit_context_build_end(context);
173:   
174:   // jit_dump_function(stderr, main_function, "main");   
175: 
  /* Execute the function and print the result */
176:   arg1 = 100000;
177:   arg2 = 50000;
178:   args[0= &arg1;
179:   args[1= &arg2;
180:   
181:   jit_function_apply(main_function, args, &result);
182:   
183:   /* Clean up */
184:   jit_context_destroy(context);
185:   
186:   /* Finished */
187:   return 0;
188: }
189: 



Общие впечатления — пишется довольно легко, документация подробная, есть примеры, так что — ставлю +

LLVM вариант


001:  #include "llvm/DerivedTypes.h"
002:  #include "llvm/LLVMContext.h"
003:  #include "llvm/Module.h"
004:  #include "llvm/Analysis/Verifier.h"
005:  #include "llvm/Support/IRBuilder.h"
006:  #include "llvm/ExecutionEngine/ExecutionEngine.h"
007:  #include "llvm/ExecutionEngine/JIT.h"
008:  #include "llvm/PassManager.h"
009:  #include "llvm/Analysis/Verifier.h"
010:  #include "llvm/Target/TargetData.h"
011:  #include "llvm/Target/TargetSelect.h"
012:  #include "llvm/Transforms/Scalar.h"
013:  
014:  #include <iostream>
015:  #include <vector>
016:  #include <list>
017:  #include <map>
018:  #include <stdlib.h>
019:  #include <cstring>
020:  #include <string>
021:  #include <stdio.h>
022:  
using namespace llvm;
023:  using namespace std;
024:  
025:  Value *ErrorV(const char *Str)
026:  {
027:      cerr << Str << endl;
028:      return 0;
029:  }
030:  
031:  static Module *TheModule;
032:  static IRBuilder <> Builder(getGlobalContext());
033:  static map < string, Value * >NamedValues;
034:  static ExecutionEngine *TheExecutionEngine;
035:  
036:  int main()
037:  {
038:      InitializeNativeTarget();
039:      LLVMContext & Context = getGlobalContext();
040:      TheModule = new Module("erato", Context);
041:  
042:      std::string ErrStr;
043:      TheExecutionEngine =
044:   EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
045:      if (!TheExecutionEngine) {
046:   fprintf(stderr, "Could not create ExecutionEngine: %s\n",
047:   ErrStr.c_str());
048:   exit(1);
049:      }
050:  
051:  
052:      const Type *voidType = Type::getVoidTy(Context);
053:      const Type *i32Type = IntegerType::get(Context, 32);
054:      const Type *i8Type = IntegerType::get(Context, 8);
055:      const Type *FType = Type::getDoubleTy(Context);
056:      const Type *SType = PointerType::get(i8Type, 0);
057:  
058:      Value *zero = ConstantInt::get(i32Type, 0);
059:      Value *one = ConstantInt::get(i32Type, 1);
060:      Value *two = ConstantInt::get(i32Type, 2);
061:      Constant *n100000 = ConstantInt::get(i32Type, 100000);
062:      Constant *n50000 = ConstantInt::get(i32Type, 50000);
063:  
064:      Value *i8zero = ConstantInt::get(i8Type, 0);
065:      Value *i8one = ConstantInt::get(i8Type, 1);
066:  
067:  
068:  
069:      vector < const Type *>def_args;
070:  
071:      def_args.push_back(SType);
072:      FunctionType *fdefinition =  FunctionType::get(voidType, def_args, true);
073:      func_printf =  Function::Create(fdefinition, GlobalValue::ExternalLinkage, "printf", TheModule);
074:      func_printf->setCallingConv(CallingConv::C);
075:      def_args.clear();
076:  
077:      // declare double @llvm.sqrt.f64(double) nounwind readonly
078:  

079:      def_args.push_back(FType);
080:      FunctionType *fdefinition_sqrt = FunctionType::get(FType, def_args, false);
081:      Function *func_sqrt = Function::Create(fdefinition_sqrt, GlobalValue::ExternalLinkage, "llvm.sqrt.f64", TheModule);
082:      func_sqrt->setCallingConv(CallingConv::C);
083:      def_args.clear();
084:  
085:      // declare void @llvm.memset.i32(i8* nocapture, i8, i32, i32) nounwind
086:  

087:      def_args.push_back(SType);
088:      def_args.push_back(i8Type);
089:      def_args.push_back(i32Type);
090:      def_args.push_back(i32Type);
091:      FunctionType *fdefinition_memset = FunctionType::get(voidType, def_args, false);
092:      Function *func_memset =  Function::Create(fdefinition_memset, GlobalValue::ExternalLinkage, "llvm.memset.i32", TheModule);
093:      func_memset->setCallingConv(CallingConv::C);
094:      def_args.clear();
095:  
096:  
097:      // Construct eratosphene()
098:  
    Function *func_ef = cast < Function > (TheModule->getOrInsertFunction("erato", voidType, i32Type, NULL));
099:      func_ef->setCallingConv(CallingConv::C);
100:      BasicBlock *ef_start_block = BasicBlock::Create(Context, "efcode", func_ef);
101:      IRBuilder <> efcodeIR(ef_start_block);
102:      format = efcodeIR.CreateGlobalStringPtr("%d"".format");
103:  
104:      BasicBlock *ef_mainloop = BasicBlock::Create(Context, "Main_loop", func_ef);
105:      BasicBlock *ef_mainloopbody = BasicBlock::Create(Context, "Main_loop.body", func_ef);
106:      BasicBlock *ef_ifbody = BasicBlock::Create(Context, "if.body", func_ef);
107:      BasicBlock *ef_whileloop = BasicBlock::Create(Context, "While_loop", func_ef);
108:      BasicBlock *ef_whileloopbody =BasicBlock::Create(Context, "While_loop.body", func_ef);
109:      BasicBlock *ef_mainloopcont = BasicBlock::Create(Context, "Main_loop.cont", func_ef);
110:      BasicBlock *ef_mainloopend =  BasicBlock::Create(Context, "Main_loop.end", func_ef);
111:  
112:      // Set name for argument
113:  
    Function::arg_iterator ef_args = func_ef->arg_begin();
114:      Argument *upbound = ef_args;
115:      upbound->setName("upbound");
116:  
117:      Value *= efcodeIR.CreateAlloca(i8Type, upbound, "a");
118:      Value *temp1 = efcodeIR.CreateUIToFP(upbound, FType, "tmp.1");
119:      Value *temp2 = efcodeIR.CreateCall(func_sqrt, temp1, "temp.2");
120:      Value *= efcodeIR.CreateFPToUI(temp2, i32Type, "q");
121:      efcodeIR.CreateCall4(func_memset, a, i8one, upbound, one);
122:      efcodeIR.CreateBr(ef_mainloop);
123:      efcodeIR.SetInsertPoint(ef_mainloop);
124:      PHINode *= efcodeIR.CreatePHI(i32Type, "i");
125:      i->addIncoming(two, ef_start_block);
126:      Value *cond = efcodeIR.CreateICmpUGT(i, q, "cond");
127:      efcodeIR.CreateCondBr(cond, ef_mainloopend, ef_mainloopbody);
128:      efcodeIR.SetInsertPoint(ef_mainloopbody);
129:      Value *eptr = efcodeIR.CreateGEP(a, i, "eptr");
130:      Value *elem = efcodeIR.CreateLoad(eptr, "elem");
131:      Value *ifcond = efcodeIR.CreateICmpEQ(i8zero, elem, "ifcond");
132:      efcodeIR.CreateCondBr(ifcond, ef_mainloopcont, ef_ifbody);
133:      efcodeIR.SetInsertPoint(ef_ifbody);
134:      Value *jfirst = efcodeIR.CreateMul(i, i, "j.first");
135:      efcodeIR.CreateBr(ef_whileloop);
136:      efcodeIR.SetInsertPoint(ef_whileloop);
137:      PHINode *= efcodeIR.CreatePHI(i32Type, "j");
138:      j->addIncoming(jfirst, ef_ifbody);
139:      Value *whilecond = efcodeIR.CreateICmpUGT(j, upbound, "while.cond");
140:      efcodeIR.CreateCondBr(whilecond, ef_mainloopcont, ef_whileloopbody);
141:      efcodeIR.SetInsertPoint(ef_whileloopbody);
142:      Value *elemref = efcodeIR.CreateGEP(a, j, "elem.ref");
143:      efcodeIR.CreateStore(i8zero, elemref);
144:      Value *jnext = efcodeIR.CreateAdd(j, i, "j.next");
145:      j->addIncoming(jnext, ef_whileloopbody);
146:      efcodeIR.CreateBr(ef_whileloop);
147:      efcodeIR.SetInsertPoint(ef_mainloopcont);
148:      Value *inext = efcodeIR.CreateAdd(i, one, "i.next");
149:      i->addIncoming(inext, ef_mainloopcont);
150:      efcodeIR.CreateBr(ef_mainloop);
151:  
152:      efcodeIR.SetInsertPoint(ef_mainloopend);
153:      efcodeIR.CreateRetVoid();
154:  
155:      // Contruct void main()
156:  
    Function *func_main = cast < Function >(TheModule->getOrInsertFunction("main", voidType, NULL));
157:      func_main->setCallingConv(CallingConv::C);
158:      BasicBlock *mnblock =  BasicBlock::Create(Context, "maincode", func_main);
159:      IRBuilder <> mainIR(mnblock);
160:  
161:      BasicBlock *mn_testloop =  BasicBlock::Create(Context, "Test_loop", func_main);
162:      BasicBlock *mn_tloopbody = BasicBlock::Create(Context, "Tloop_body", func_main);
163:      BasicBlock *mn_endloop =   BasicBlock::Create(Context, "End_loop", func_main);
164:  
165:      mainIR.CreateBr(mn_testloop);
166:      mainIR.SetInsertPoint(mn_testloop);
167:      PHINode *maini = mainIR.CreatePHI(i32Type, "i");
168:      maini->addIncoming(zero, mnblock);
169:      Value *mainloopcond =mainIR.CreateICmpUGT(maini, n100000, "loop_cond");
170:      mainIR.CreateCondBr(mainloopcond, mn_endloop, mn_tloopbody);
171:      mainIR.SetInsertPoint(mn_tloopbody);
172:      mainIR.CreateCall(func_ef, n50000);
173:      Value *maininext = mainIR.CreateAdd(maini, one, "i.next");
174:      maini->addIncoming(maininext, mn_tloopbody);
175:      mainIR.CreateBr(mn_testloop);
176:      mainIR.SetInsertPoint(mn_endloop);
177:      mainIR.CreateRetVoid();
178:  
179:      TheModule->dump();
180:  
181:      void *FPtr = TheExecutionEngine->getPointerToFunction(func_main);
182:      void (*FP) () = (void (*)()) FPtr;
183:      FP();
184:  }
185:  


Итак, сравниваем:

По многословности — практически ноздря в ноздрю. И там и там можно выкинуть пару строк/комментариев или добавить пару строк, но это не делает погоды — размер кода получился примерно одинковый.

По скорости
LibJit вариант:

walrus@home:~/sand/erato$ gcc t2_test.c -o ts -ljit
walrus@home:~/sand/erato$ for i in `seq 1 10`; do /usr/bin/time -f '%U' ./ts; done
14.22
14.17
14.12
14.19
14.18
14.24
14.15
14.14
14.15
14.15

Среднее значение 14.17 секунд

LLVM вариант —
walrus@home:~/sand/erato/llvm$ g++ ts.cc -o ts `llvm-config --cxxflags --libs` -lrt -ldl
walrus@home:~/sand/erato/llvm$ for i in `seq 1 10`; do /usr/bin/time -f '%U' ./ts; done
13.83
13.75
13.82
13.76
13.76
13.78
13.76
13.76
13.76
13.76

Среднее значение — 13.77 секунд.

Разница составила 2.88% в пользу llvm.

Кстати, аналогичная C программа, приготовленная с помощью gcc -O1 дала те же 13.79 секунд.

По засадам — у llvm неприятных особенностей незамечено. У libjit — эта собака не сохраняет значение регистров при вызове функции! Все что надо, чтобы осталось целым, лучше сохранять в памяти перед вызовом любой функции. Как своей jibjit-овской, так и внешней. В документации я этого не нашел, и потратил пару часов, пытаясь понять, что же это за беда такая. Окончательно проблему прояснило только рассматривание сгенерированного ассемблера.

Мораль



Ээ… что-то не соображу, какая тут мораль
Tags:
Hubs:
+4
Comments 5
Comments Comments 5

Articles