kouzdra (kouzdra) wrote,
kouzdra
kouzdra

"Старое как говно мамонта"

Вообще к вопросу о том насколько subj (тоже примерно 99-2000 год):

Date:	-- (:)
From:	Anton Moscal 
Subject:	O'Caml native code can be easily improved in size by 10%
Hello!

Subj.

In functional languages many sequential constructors frequently occur. Each 
constructor with arguments causes memory allocation. For example:

    let f x y z = [x+y;y+z;z+x]

compiled by O'Caml into the following (real code for x86 placed at the end of 
the message) code:

	t  := alloc list item ; t.cdr  := NIL; 	t.car  := z+x
	t' := alloc list item ; t'.cdr := t; 	t'.car := y+z
	t" := alloc list item ; t".cdr := t'; 	t".car := x+y
	return t"

For x86 each allocation takes 6 commands:

.L101:	movl	young_ptr, %eax
	subl	$12, %eax
	movl	%eax, young_ptr
	cmpl	young_limit, %eax
	jb	.L102
	leal	4(%eax), %edx

(and also `caml_call_gc; jmp .L101' at the function end, and frame for GC with 
approx 8-16B size) - total about 40B.

If we allocate memory for all 3 list items by one request, then we can replace 
each of the two last allocations by the following:

       mov young_ptr, %eax
       lea offset(%eax), %reg

8B and nothing more.
	
This optimization is valid only in basic blocks and olny if code between
allocations can't call a garbage collection.

I made it. This takes about 90 lines of added/changed code in compiler
(together with the two changes described below). This optimization
reduces code size of ocamlopt.opt+ocamlc.opt by 8.7%. I think this is an
excellent result for 90-lines changes.

Bootstrapping of ocamlopt.opt was successfull. This means that my changes
are correct, I hope.

This is an optimization which can be applied to all architectures. For  
architectures with `young_ptr' in the memory (x86, m68k) yet another
improvement exists: in many cases instead of loading `young_ptr' from 
memory we can use address of the object created by previous constructor which 
is `young_ptr + offset' and is frequently located in one of the registers 
because it is the argument of the constructor following it. In this case we 
eliminate the first of the two remaining commands. This optimization 
reduces ocamlopt.opt+ocamlc.opt code for x86 by 1.6%.

And the last: on x86 and m68k architectures `selection.ml' contains the
following method:

method select_store addr exp =
  match exp with
    Cconst_int n -> (Ispecific(Istore_int(n, addr)), Ctuple [])
  | Cconst_pointer n -> (Ispecific(Istore_int(n, addr)), Ctuple [])
  | Cconst_symbol s -> (Ispecific(Istore_symbol(s, addr)), Ctuple [])
  | _ -> super#select_store addr exp

the alternative
    Cconst_int n -> (Ispecific(Istore_int(n, addr)), Ctuple [])

processes storing of the Cconst_int immediate constants, but ignores the  
Cconst_natint constants. This causes generating the following bad code  
immediately after each memory allocation:

	mov	$tag, %r1
	mov	%r1, -4(%r2)

instead of a better:

	mov	$tag, -4(%r2).

I fixed this by adding the following match pattern:

  | Cconst_natint n 
      when Nativeint.cmp n min_int >= 0  
      &&   Nativeint.cmp n max_int <= 0 
    ->
      (Ispecific(Istore_int(Nativeint.to_int n, addr)), Ctuple [])

This change improves code size of ocamlc.opt+ocamlopt.opt by yet 0.7%.
The same change needed for m68k.
A better solution probably will be to add the operator Istore_natint.


I estimated the number of memory allocations in ocamlopt.opt+ocamlc.opt. 
I found about 12,000 memory allocations approximately 7,000 of which is the 
subject of the described optimizations.

Table of code sizes:

             old size:   new size-1:     new size-2:     new size-3:   total:
-----------------------------------------------------------------------------
ocamlopt.opt:1,061,028   971,229 8.46%   956,173 1.57%   949,421 0.71% 10.52%
  ocamlc.opt:1,375,599 1,254,322 8.82% 1,234,178 1.61% 1,225,434 0.69% 10.90%
  ocamlc+opt:2,436,627 2,225,551 8.66% 2,190,351 1.58% 2,175,027 0.70% 10.74%

Patches with changes in the compiler are attached to this message in the
file ocaml-2.01.patch.gz

=================================================

Appendix: code for function
	let f a b c = [a+b; b+c; c+a]

Optimized code:

T_f_39:
.L100:
	movl	%eax, %edi
.L101:	movl	young_ptr, %eax
	subl	$36, %eax
	movl	%eax, young_ptr
	cmpl	young_limit, %eax
	jb	.L102
	leal	4(%eax), %edx
	movl	$2048, -4(%edx)
	lea	-1(%ecx, %edi), %eax
	movl	%eax, (%edx)
	movl	$1, 4(%edx)

        leal	12(%edx), %esi
	movl	$2048, -4(%esi)
	lea	-1(%ebx, %ecx), %eax
	movl	%eax, (%esi)
	movl	%edx, 4(%esi)

        leal	12(%esi), %eax
	movl	$2048, -4(%eax)
	lea	-1(%edi, %ebx), %ebx
	movl	%ebx, (%eax)
	movl	%esi, 4(%eax)
	ret
.L102:	call	caml_call_gc
.L103:	jmp	.L101

	.long	.L103
	.word	4
	.word	3
	.word	5
	.word	3
	.word	11
	.align	4


Original code:

T_f_38:
.L100:
	movl	%eax, %edi
.L101:	movl	young_ptr, %eax
	subl	$12, %eax
	movl	%eax, young_ptr
	cmpl	young_limit, %eax
	jb	.L102
	leal	4(%eax), %edx
	movl	$2048, %eax
	movl	%eax, -4(%edx)
	lea	-1(%ecx, %edi), %eax
	movl	%eax, (%edx)
	movl	$1, 4(%edx)

.L104:	movl	young_ptr, %eax
	subl	$12, %eax
	movl	%eax, young_ptr
	cmpl	young_limit, %eax
	jb	.L105
	leal	4(%eax), %esi
	movl	$2048, %eax
	movl	%eax, -4(%esi)
	lea	-1(%ebx, %ecx), %eax
	movl	%eax, (%esi)
	movl	%edx, 4(%esi)

.L107:	movl	young_ptr, %eax
	subl	$12, %eax
	movl	%eax, young_ptr
	cmpl	young_limit, %eax
	jb	.L108
	leal	4(%eax), %eax
	movl	$2048, %ecx
	movl	%ecx, -4(%eax)
	lea	-1(%edi, %ebx), %ebx
	movl	%ebx, (%eax)
	movl	%esi, 4(%eax)

	ret

.L108:	call	caml_call_gc
.L109:	jmp	.L107
.L105:	call	caml_call_gc
.L106:	jmp	.L104
.L102:	call	caml_call_gc
.L103:	jmp	.L101

	.long	.L109
	.word	4
	.word	3
	.word	9
	.word	3
	.word	11
	.align	4
	.long	.L106
	.word	4
	.word	4
	.word	7
	.word	5
	.word	3
	.word	11
	.align	4
	.long	.L103
	.word	4
	.word	3
	.word	5
	.word	3
	.word	11
	.align	4

============================================================

Regards,
Anton E.Moscal

На это кстати последовал немедленный ответ и предлагаемые патч был иинкорпорирован в ближайший релиз Ocaml (хоть естественно не в таком виде - XL все-таки лучше знал куда там надо это вставлять).

Упомянутый CoQ там был у меня на пару с самим компилятором главным тестбенчем - "если и он после моих грязных хаков заработает - значит я ничего серьезно там не сломал" - заработал - и оекономию по коду на Петухе дал даже больше - около 15% емнимп)

Но вообще говоря - странно даже не то, что чувствовать себя динозавром - странно то, что вот это все закаменелое говно конца прошлого века до сих пор "передний край компутерной науки".

Тойсть у мну проблема что таки да - на ветке ML-CaML-OCaml-Dependent ML-ATS выросло нечто нетривиальное - но мне трудно это заметить потому что я все эти окаменелости знаю и что там что-то особенное может прорасти в общем не жду (хотя тут слава Путину (без шуток кстати) извне обратили внимание - ну и оценил) - но норот ведь в основном и об этом не думает.

Да - этот пост проплачен за 83 рубли.
Слава Путину!
PS: А если серьезно - то вот правда - причиной моего начального интереса (потом пошел собственный) было именно - "а вот посмотри что щас с верификацией формальной в мире происходит - и особенно на ATS посмотри - потом расскажешь и может поможешь бумажку с предложениями для заказчика написать"

Ситуация как раз радикально отличающаяся от 15-летней давности, когда всем на такие вещи было просто пох - "мы все купим". А тут - спрос есть, хоть и непростой.

Кстати сильное отличие нынешней путинской россии от ельцинской-постельцинской - восстанавливается квалифицированный спрос. С околовоенных вестимо - а по другому и не бывает - если у вас есть армия и нет квалифицированного военного спроса - у вас и никакого нет (исключения - мини-республики которым повезло встроиться в международное разделение труда в прибыльную позицию - типа Швейцарии - хотя и ее встраивание основано на войне - автомат с запасом патроном под кроватью и налог на уклонистов как бе намекают)
Subscribe

  • "Вам Шура не завидно? Мне завидно"

    Ко Дню Победы, Илон Маск и компания SpaceX осуществили десятый повторный полет первой ступени. Ускоритель Falcon 9 Block 5 под номером B1051 поднялся…

  • "Иликой пабеды прозник"

    Щас subj положено плясать - хотя нынешняя россияния имеет к нему примерно столько же как и украиния. Эту войну выиграли совсем другие страны. И…

  • Вдогонку к предыдущему:

    Экспедицию Франклина на "Эребусе" и "Терроре" убил imho именно социальный распад группы - если бы не он - остальное все можно было бы пусть и с…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments