たとえば、Javaと同じくらい効率的です。具体的には、単純なトリプルループ、単精度、連続した列優先レイアウト（float [][]ではなくfloat[]）、サイズ1000x1000の行列、およびシングルコアCPUについて話していると仮定します。（サイクルごとに0.5〜2の浮動小数点演算を取得している場合は、おそらく球場にいます）
だから何かのような
public class MatrixProd {
static float[] matProd(float[] a, int ra, int ca, float[] b, int rb, int cb) {
if (ca != rb) {
throw new IllegalArgumentException("Matrices not fitting");
}
float[] c = new float[ra*cb];
for(int i = 0; i < ra; ++i) {
for(int j = 0; j < cb; ++j) {
float sum = 0;
for(int k = 0; k < ca; ++k) {
sum += a[i*ca+k]*b[k*cb+j];
}
c[i*cb+j] = sum;
}
}
return c;
}
static float[] mkMat(int rs, int cs, float x, float d) {
float[] arr = new float[rs*cs];
for(int i = 0; i < rs; ++i) {
for(int j = 0; j < cs; ++j) {
arr[i*cs+j] = x;
x += d;
}
}
return arr;
}
public static void main(String[] args) {
int sz = 100;
float strt = -32, del = 0.0625f;
if (args.length > 0) {
sz = Integer.parseInt(args[0]);
}
if (args.length > 1) {
strt = Float.parseFloat(args[1]);
}
if (args.length > 2) {
del = Float.parseFloat(args[2]);
}
float[] a = mkMat(sz,sz,strt,del);
float[] b = mkMat(sz,sz,strt-16,del);
System.out.println(a[sz*sz-1]);
System.out.println(b[sz*sz-1]);
long t0 = System.currentTimeMillis();
float[] c = matProd(a,sz,sz,b,sz,sz);
System.out.println(c[sz*sz-1]);
long t1 = System.currentTimeMillis();
double dur = (t1-t0)*1e-3;
System.out.println(dur);
}
}
私は考えます？（コーディング前に仕様を正しく読んでいなかったので、レイアウトは行優先ですが、アクセスパターンが同じであるため、混合レイアウトの場合と違いはありません。それで問題ないと思います。）
私は巧妙なアルゴリズムや低レベルの最適化のトリックについて考えることに時間を費やしていません（とにかくそれらを使ってJavaで多くを達成することはありません）。単純なループを書いただけです。
これが挑戦のように聞こえたくないのですが、Javaは上記のすべてを簡単に満たすことができることに注意してください
そして、それはJavaが簡単に提供するものなので、私はそれを取り上げます。
（サイクルごとに0.5〜2の浮動小数点演算を取得している場合は、おそらく球場にいます）
JavaでもHaskellでも、私は恐れています。単純なトリプルループでそのスループットに到達するには、キャッシュミスが多すぎます。
Haskellでも同じことをしますが、これも賢いことを考えずに、単純で単純なトリプルループです。
{-# LANGUAGE BangPatterns #-}
module MatProd where
import Data.Array.ST
import Data.Array.Unboxed
matProd :: UArray Int Float -> Int -> Int -> UArray Int Float -> Int -> Int -> UArray Int Float
matProd a ra ca b rb cb =
let (al,ah) = bounds a
(bl,bh) = bounds b
{-# INLINE getA #-}
getA i j = a!(i*ca + j)
{-# INLINE getB #-}
getB i j = b!(i*cb + j)
{-# INLINE idx #-}
idx i j = i*cb + j
in if al /= 0 || ah+1 /= ra*ca || bl /= 0 || bh+1 /= rb*cb || ca /= rb
then error $ "Matrices not fitting: " ++ show (ra,ca,al,ah,rb,cb,bl,bh)
else runSTUArray $ do
arr <- newArray (0,ra*cb-1) 0
let outer i j
| ra <= i = return arr
| cb <= j = outer (i+1) 0
| otherwise = do
!x <- inner i j 0 0
writeArray arr (idx i j) x
outer i (j+1)
inner i j k !y
| ca <= k = return y
| otherwise = inner i j (k+1) (y + getA i k * getB k j)
outer 0 0
mkMat :: Int -> Int -> Float -> Float -> UArray Int Float
mkMat rs cs x d = runSTUArray $ do
let !r = rs - 1
!c = cs - 1
{-# INLINE idx #-}
idx i j = cs*i + j
arr <- newArray (0,rs*cs-1) 0
let outer i j y
| r < i = return arr
| c < j = outer (i+1) 0 y
| otherwise = do
writeArray arr (idx i j) y
outer i (j+1) (y + d)
outer 0 0 x
および呼び出し元モジュール
module Main (main) where
import System.Environment (getArgs)
import Data.Array.Unboxed
import System.CPUTime
import Text.Printf
import MatProd
main :: IO ()
main = do
args <- getArgs
let (sz, strt, del) = case args of
(a:b:c:_) -> (read a, read b, read c)
(a:b:_) -> (read a, read b, 0.0625)
(a:_) -> (read a, -32, 0.0625)
_ -> (100, -32, 0.0625)
a = mkMat sz sz strt del
b = mkMat sz sz (strt - 16) del
print (a!(sz*sz-1))
print (b!(sz*sz-1))
t0 <- getCPUTime
let c = matProd a sz sz b sz sz
print $ c!(sz*sz-1)
t1 <- getCPUTime
printf "%.6f\n" (fromInteger (t1-t0)*1e-12 :: Double)
したがって、両方の言語でほぼ同じことを行っています。Haskellをでコンパイルし-O2、Javaをjavacでコンパイルします
$ java MatrixProd 1000 "-13.7" 0.013
12915.623
12899.999
8.3592897E10
8.193
$ ./vmmult 1000 "-13.7" 0.013
12915.623
12899.999
8.35929e10
8.558699
そして、結果として生じる時間は非常に近いです。
そして、Javaコードをネイティブにコンパイルするとgcj -O3 -Wall -Wextra --main=MatrixProd -fno-bounds-check -fno-store-check -o jmatProd MatrixProd.java、
$ ./jmatProd 1000 "-13.7" 0.013
12915.623
12899.999
8.3592896512E10
8.215
まだ大きな違いはありません。
特別なボーナスとして、Cの同じアルゴリズム（gcc -O3）：
$ ./cmatProd 1000 "-13.7" 0.013
12915.623047
12899.999023
8.35929e+10
8.079759
したがって、これは、浮動小数点数を使用する計算集約型タスクに関して、単純なJavaと単純なHaskellの基本的な違いを明らかにしません（中規模から大規模の数値で整数演算を処理する場合、GHCによるGMPの使用により、HaskellはJavaのBigIntegerを大幅に上回ります多くのタスクで使用できますが、これはもちろんライブラリの問題であり、言語の問題ではありません）。このアルゴリズムでは、どちらもCに近いものです。
ただし、公平を期すために、アクセスパターンによって1ナノ秒おきにキャッシュミスが発生するため、3つの言語すべてで、この計算はメモリに依存します。
行メジャーマトリックスと列メジャーマトリックスを乗算してアクセスパターンを改善すると、すべてが高速になり、gccコンパイルされたCは1.18秒、javaは1.23秒、ghcコンパイルされたHaskellは約5.8秒かかります。 llvmバックエンドを使用することで3秒に短縮できます。
ここで、配列ライブラリによる範囲チェックは本当に痛いです。チェックされていない配列アクセスを使用すると（バグをチェックした後、ループを制御するコードでチェックがすでに行われているため）、GHCのネイティブバックエンドは2.4秒で終了し、llvmバックエンドを経由すると1.55秒で計算が終了します。これはまともですが、CとJavaの両方よりも大幅に低速です。配列GHC.Primライブラリの代わりにからのプリミティブを使用して、llvmバックエンドは1.16秒で実行されるコードを生成します（ここでも、各アクセスで境界チェックは行われませんが、計算中に有効なインデックスのみが生成されることは、この場合、前に簡単に証明できます。したがって、ここでは、メモリの安全性が犠牲になることはありません¹。各アクセスをチェックすると、最大1.96秒の時間がかかります。これは、アレイの境界チェックよりもはるかに優れています。図書館）。
結論：GHCは境界チェックのために（はるかに）高速な分岐を必要とし、オプティマイザーには改善の余地がありますが、原則として、「Haskellのアプローチ（型システムでエンコードされた純度）は、効率、メモリ安全性、および単純性と互換性があります「、私たちはまだそこにいません。当面は、どのポイントをどれだけ犠牲にしても構わないと思っているかを決める必要があります。
¹はい、これは特殊なケースです。一般に、境界チェックを省略すると、メモリの安全性が犠牲になります。そうでないことを証明するのは、少なくとも困難です。