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.