バイトふるい

Byte Sieve は、プログラミング言語のパフォーマンス ベンチマークとしてByteが公開したエラトステネスの篩のコンピュータ ベースの実装です。このベンチマークは、1981 年 9 月号の同誌に初めて掲載され、その後もたびたび取り上げられました。同じコンピュータ上で異なる言語のパフォーマンスを比較することを目的としていましたが、すぐに広く使用されるマシン ベンチマークになりました。

Sieve は、ホーム コンピュータ時代の最も人気のあったベンチマークの 1 つであり、他には1983 年のCreative Computing Benchmarkや、この時代に主にイギリスで見られたRugg/Feldman ベンチマークなどがあります。Byteは、その後 1995 年に、より徹底したNBench をリリースして、これに代わるものとなりました。

海軍海洋システムセンターのジム・ギルブレスは、以前から小さな言語ベンチマークプログラムを書くという構想を検討していた。彼は、言語間で移植可能で、プログラムコードが1ページに収まるほど小さく、ハードウェアの乗算や除算などの特定の機能に依存しないプログラムを望んでいた。この解決策は、1980年1月にコロラド州ボルダーで開催されたUSENIX会議でのチャック・フォースバーグとの会議に触発された。フォースバーグは、ドナルド・クヌースが書いたふるいの実装について言及した。^{[1] [2]}

ギルブレスは、システム間で大きく異なる演算性能の間接的なテストを避けることができるため、ふるいが理想的なベンチマークになると感じました。このアルゴリズムは、主に配列検索性能と基本的なロジックおよび分岐機能を重視しています。また、再帰や高度なコレクション型などの高度な言語機能も必要としません。クヌースのオリジナルバージョンからの唯一の変更点は、2 倍の乗算を削除し、代わりに加算に置き換えたことです。オリジナルバージョンでは、ハードウェア乗算器を備えたマシンは、それ以外の点でははるかに高速に動作するため、残りのパフォーマンスは隠れてしまいます。^[1]

6か月間、アクセスできる限り多くのプラットフォームに移植する作業を行った後、最初の成果が1981年9月号のByte誌で「高水準言語ベンチマーク」と題する記事として紹介されました。^[1]ギルブレスはすぐに次のように指摘しました。

このベンチマークは言語やコンパイラを評価する唯一の基準ではないことを強調しておきます。^[1]

論文では、BASIC、C、Pascal、COBOL、FORTRANなどの人気の高い言語や、 Forth、ZSPL、Ratfor、PL/1、PLMXなどのあまり知られていない言語を含む10の言語でのリファレンス実装が紹介されました。^[3]

実行例はさまざまなマシンで提供されましたが、そのほとんどはZilog Z80またはMOS 6502ベースでした。当初の最高記録は、4 MHz の Z80 マシンで Ratfor が出した 16.5 秒でしたが、Gary Kildall がDigital Researchの PL/1 のプロトタイプ バージョン^[4]で個人的に提供したバージョンは14 秒で実行され、この最初のコレクションの記録となりました。最も遅かったのは同じマシン上の Microsoft COBOL で、なんと 5115 秒 (約 1 時間半) かかり、BASIC などのインタープリタ言語よりも長くなりました。^[5]この最初の実行の注目すべき特徴は、C、Pascal、PL/1 のすべてがほぼ同様のパフォーマンスを示し、さまざまなインタープリタを簡単に上回ったことです。^[4]

2 回目のテストはより強力なマシンで実行され、モトローラ 68000 アセンブリ言語が1.12 秒という最速タイムを記録しました。これはPDP-11/70の C をわずかに上回り、8086 アセンブラのほぼ 2 倍の速さでした。PDP-11 とHP-3000 のほとんどの時間は 10 秒から 50 秒程度と、はるかに遅いものでした。^[6]これらのマシンで高級言語のみを使用したテストでは、PDP-11 の NBS Pascal が 2.6 秒でトップでした。^[7]

UCSD Pascal は、同じプログラムを複数のマシンで実行できるという、もう 1 つの興味深い結果をもたらしました。Pascal MicroEngineベースのコンピュータである専用のIthaca InterSystems Pascal-100 マシンで実行すると、54 秒で実行されましたが、Z80 では 239 秒、Apple II では 516 秒でした。^[7]

ギルブレスは今度は弟のゲイリーとともに、1983年1月号のByteでコードを再検討した。このバージョンでは、あまり人気のない言語のほとんどが削除され、Pascal、C、FORTRAN IV、COBOLが残り、AdaとModula-2が追加された。読者が追加のサンプルを提供してくれたおかげで、結果の表で比較されるマシン、オペレーティングシステム、言語の数が大幅に増えた。^[8]

モトローラ 68000 (68k) アセンブリは依然として最速で、同じ 8 MHz クロックで動作するIntel 8086のほぼ 3 倍の速度でした。高級言語を使用すると、両者のパフォーマンスは近づき、8086 は一般に 68k の半分以下の速度で、それよりはるかに近いことが多かったです。^[9]より幅広い種類のミニコンピュータとメインフレームも含まれており、 IBM 3033やVAXのハイエンド モデルなどの最速マシンを除いて、一般に 68k がタイムを上回っていました。Data General Nova、PDP-11、HP-1000などの古いマシンは、68k に遠く及びませんでした。^[8]

ギルブレスの2番目の論文は、ベンチマークが言語だけでなく、さまざまなマシンのパフォーマンスを比較する方法としてかなり一般的になりつつあったときに発表されました。彼は当初そうしないように警告していましたが、すぐに雑誌の広告で競合製品とパフォーマンスを比較する方法として、^{[10] [11]}および一般的なベンチマークとして掲載されるようになりました。^[12]

1983年8月後半、 Byte誌はC言語に関する雑誌連載記事の一環として、このふるいを再び取り上げた。このときの使用法は、より当初の意図に沿ったもので、単一のソースコードを単一のマシンで実行し、CP/M-86オペレーティングシステム、^[13] CP/M-80、^[14] IBM PC ^[15]のCコンパイラのパフォーマンスを比較した。

ギルブレスが最初の記事で懸念を表明したにもかかわらず、この頃にはコードはテストにほぼ普遍的になっており、記事の1つでは「エラトステネスの篩は必須のベンチマークである」と述べられていた。^[13]これは1984年8月に導入されたByte UNIXベンチマークスイートに含まれていた。 ^[16]

新しい言語向けの新しいバージョンのコードが次々と登場しています。 ^[17]例えば、Rosetta CodeやGitHubには多くのバージョンがあります。^[18]一般的なバージョンでは実際にはふるいアルゴリズムを使用していないにもかかわらず、関数型プログラミングの例としてよく使用されます。 ^[19]

提供された実装では奇数の素数のみを計算したため、8191 要素の配列は実際には 16385 未満の素数を表します。サイドバーの表に示されているように、0 番目の要素は 3、1 番目の要素は 5、2 番目の要素は 7 などを表します。

これは1981年に発表されたコードのオリジナルのBASICバージョンです。^{[20] [a]}方言は指定されていませんが、やのような長い変数名の使用など、いくつかの詳細から、 Microsoft BASICの初期バージョン（4.x以前）では動作しないことがわかります。行番号がないことから、テキストファイルからソースを読み込むミニコンピュータのバージョンであることが考えられますが、印刷エラーである可能性もあります。 SIZEFLAGS

REM エラトステネスのふるい素数 BASIC プログラム
1 SIZE = 8190 2 DIM FLAGS ( 8191 ) 3 PRINT "Only 1 iteration" 5 COUNT = 0 6 FOR I = 0 TO SIZE 7 FLAGS ( I ) = 1 8 NEXT I 9 FOR I = 0 TO SIZE 10 IF FLAGS ( I ) = 0 THEN 18 11 PRIME = I + I + 3 12 K = I + PRIME 13 IF K > SIZE THEN 17 14 FLAGS ( K ) = 0 15 K = K + PRIME 16 GOTO 13 17 COUNT = COUNT + 1 18 NEXT I 19 PRINT COUNT , " PRIMES"   
  
  
   
      
    
  
      
       
     
     
      
    
     
  
     
  
  

Cでは、オリジナルから空白を調整した次のようになります。^[21]

#define true 1 
#define false 0 
#define size 8190 
#define sizepl 8191 
char flags [ sizepl ]; main () { int i , prime , k , count , iter ; printf ( "10 iterations \n " ); for ( iter = 1 ; iter <= 10 ; iter ++ ) { count = 0 ; for ( i = 0 ; i <= size ; i ++ ) flags [ i ] = true ; for ( i = 0 ; i <= size ; i ++ ) { if ( flags [ i ]) { prime = i + i + 3 ; k = i + prime ; while ( k <= size ) { flags [ k ] = false ; k += prime ; } count = count + 1 ; } } } printf ( " \n %d 個の素数" ,カウント); } 
 
          
    
             
          
               
               
                 
              
                       
                     
                     
                       
                       
                
                    
            
        
    
     

• Gilbreath, Jim (1981 年 9 月)。「高水準言語ベンチマーク」。Byte。pp . 180–198。
• ギルブレス、ジム; ギルブレス、ゲイリー (1983 年 1 月)。「エラトステネス再考: ふるいをもう一度通して」。バイト。pp. 283–325。
• クヌース、ドナルド (1969)。『コンピュータプログラミングの技法 第2巻: 半数値アルゴリズム』Addison- Wesley。ISBN 978-0-201-89684-8。