performance - GHC generando operaciones centrales redundantes

haskell core

Question

Tengo el siguiente programa para convertir 6bit ASCII a formato binario.

ascii2bin :: Char -> B.ByteString
ascii2bin = B.reverse . fst . B.unfoldrN 6 decomp . to6BitASCII -- replace to6BitASCII with ord if you want to compile this
where decomp n = case quotRem n 2 of (q,r) -> Just (chr r,q)
bs2bin :: B.ByteString -> B.ByteString
bs2bin = B.concatMap ascii2bin

esto produce el siguiente segmento de núcleo:

Rec {
$wa
$wa =
/ ww ww1 ww2 w ->
case ww2 of wild {
__DEFAULT ->
let {
wild2
wild2 = remInt# ww1 2 } in
case leWord# (int2Word# wild2) (__word 1114111) of _ {
False -> (lvl2 wild2) `cast` ...;
True ->
case writeWord8OffAddr#
ww 0 (narrow8Word# (int2Word# (ord# (chr# wild2)))) w
of s2 { __DEFAULT ->
$wa (plusAddr# ww 1) (quotInt# ww1 2) (+# wild 1) s2
}
};
6 -> (# w, (lvl, lvl1, Just (I# ww1)) #)
}
end Rec }

note que ord . chr == id ord . chr == id , y aquí hay una operación redundante aquí: narrow8Word# (int2Word# (ord# (chr# wild2)))

¿Hay alguna razón por la que GHC esté convirtiendo innecesariamente de Int -> Char -> Int, o es un ejemplo de generación de código deficiente? ¿Se puede optimizar esto?

EDITAR: Esto está usando GHC 7.4.2, no he intentado compilar con ninguna otra versión. Desde entonces he encontrado que el problema sigue en GHC 7.6.2, pero las operaciones redundantes se eliminan en la rama HEAD actual en github.

Answer 1

¿Hay alguna razón por la que GHC esté convirtiendo innecesariamente de Int -> Char -> Int , o es un ejemplo de generación de código deficiente? ¿Se puede optimizar esto?

En realidad no (a ambos). El núcleo que obtienes de -ddump-simpl no es el final. Hay algunas optimizaciones y transformaciones que aún se realizan después de eso en el camino hacia el código de ensamblaje. Pero eliminar las conversiones redundantes aquí no es realmente una optimización.

Pueden ser, y son, removidos entre el núcleo y el ensamblaje. El punto es que estos primops, excepto el estrechamiento, no son operaciones, solo están presentes en el núcleo porque eso está escrito. Como no son operativos, no importa si hay una cadena redundante de ellos en el núcleo.

El ensamblaje que produce 7.6.1 a partir del código [es más legible que lo que produce 7.4.2, así que lo tomo] - con ord lugar de to6BitASCII - es

ASCII.$wa_info:
_cXT:
addq $64,%r12
cmpq 144(%r13),%r12
ja _cXX
movq %rdi,%rcx
cmpq $6,%rdi
jne _cXZ
movq $GHC.Types.I#_con_info,-56(%r12)
movq %rsi,-48(%r12)
movq $Data.Maybe.Just_con_info,-40(%r12)
leaq -55(%r12),%rax
movq %rax,-32(%r12)
movq $(,,)_con_info,-24(%r12)
movq $lvl1_rVq_closure+1,-16(%r12)
movq $lvl_rVp_closure+1,-8(%r12)
leaq -38(%r12),%rax
movq %rax,0(%r12)
leaq -23(%r12),%rbx
jmp *0(%rbp)
_cXX:
movq $64,192(%r13)
_cXV:
movl $ASCII.$wa_closure,%ebx
jmp *-8(%r13)
_cXZ:
movl $2,%ebx
movq %rsi,%rax
cqto
idivq %rbx
movq %rax,%rsi
cmpq $1114111,%rdx
jbe _cY2
movq %rdx,%r14
addq $-64,%r12
jmp GHC.Char.chr2_info
_cY2:
movb %dl,(%r14)
incq %r14
leaq 1(%rcx),%rdi
addq $-64,%r12
jmp ASCII.$wa_info
.size ASCII.$wa_info, .-ASCII.$wa_info

La parte en la que aparece en el núcleo la cmpq $1114111, %rdx narrow8Word# (int2Word# (ord# (chr# wild2))) aparece después del cmpq $1114111, %rdx . Si el cociente no está fuera de rango, el código salta a _cY2 que ya no contiene tales conversiones. Se escribe un byte en la matriz, algunos punteros / contadores se incrementan, y eso es todo, salte de nuevo a la parte superior.

Creo que sería posible generar un mejor código a partir de lo que hace GHC actualmente, pero las conversiones no operativas redundantes ya desaparecen.