base64の驚くほど高速なエンコードとデコード

著者について:Daniel Lemerは、ケベック大学(カナダ)のコンピューターサイエンスの教授です。 彼の研究は、ソフトウェアパフォーマンスとデータエンジニアリングを対象としています。



コンピューターはデータをビットのストリームとして保存します。 イメージ、オーディオまたはビデオファイル、およびバイナリファイルの両方に、ほぼすべてのビットシーケンスを含めることができます。



ただし、多くの場合、テキスト形式を使用します。 たとえば、Webページと電子メールはテキスト形式である必要があります。 電子メールで画像を送信するにはどうすればよいですか? Webページに画像を埋め込むにはどうすればよいですか? 1つのオプションは、実際のバイナリファイルへのリンクを配置することです。 別の典型的なアプローチは、 base64を使用して電子メールまたはWebページの本文に直接バイナリファイルを埋め込むことです。 Base64は、バイナリデータのエンコードに使用できる標準のテキスト形式です。 正確には、base64コードは常に有効なASCIIテキストです(したがって有効なUTF-8)。 base64コードの各バイトには、6ビットのデータが含まれています。 つまり、1バイトあたり約2ビットを「失います」。 したがって、バイナリファイルに相当するbase64は約33%大きくなります。 実際には、このようなサイズの増加が問題になることはほとんどありません。 私の知る限り、電子メールの添付ファイルはほとんど常にbase64でエンコードされています。



HTMLを記述するとき、 データURIスキームを使用して画像をHTMLに直接埋め込むと便利です。 たとえば、 最近の記事では、PNGファイルをこの方法でエンコードしました。 Googleのような大規模なWebサイトは常にこのスキームを使用しています。 小さな欠点は、Webページのサイズがわずかに大きく(明らか)、画像キャッシュを利用できないことです。 ただし、ブラウザーは1つのネットワーク要求を保存します。



Web開発者の場合、 Web Storageを使用して、クライアント側でアプリケーションのデータベースを作成できます。 このクライアントデータベースには画像と任意のデータが保存されますが、それらはすべてbase64でエンコードする必要があります。



ほとんどのデータベースエンジンはバイナリデータをサポートしますが、ある時点でbase64エンコードが必要なものもあります。これらはMongoDB、Elasticsearch、Amazon SimpleDB、およびAmazon DynamoDBです。 おそらくもう少し。



Base64は、鍵交換の暗号化で広く使用されています。 base64形式は、URIの一部として任意のデータを転送するためにも使用されます。



幸いなことに、base64のエンコードとデコードは高速です。 不十分な速度が問題になる場合がありますが。 Matt CraneとJimmy Linは、Amazon DynamoDBでbase64バイナリ属性のデコードが遅いことを発見しました



base64データをデコードする速度はどれくらいですか? 最新のIntelプロセッサーでは、Chromeブラウザーに組み込まれているような高速デコーダーを使用する場合、これには1バイトあたり約2サイクル(キャッシュから)が必要です。 この高速デコーダは、主にテーブル呼び出しでビジーです。 これは、キャッシュ内のデータをコピーするよりもはるかに遅くなります(バイトあたり0.05サイクル未満です)。



これはあなたが得ることができる最高のものですか?



数年前、Alfred Klopp 、ベクトル命令を使用するとはるかに優れた結果を達成できることを示しました。 Wojciech Mula、私、そして何人かの同僚(HowardとKurtzを含む)は、この問題を真剣に検討することにしました。 Mulaはこのトピック専用のWebページを開きました。



ベクター命令を使用すると、最新のIntelプロセッサーで処理を10倍高速化し、バイトあたり約0.2サイクルしか使用できないことがわかりました。 これはまだコピー以上のものですが、システムのボトルネックになる可能性のある制限よりはるかに少ないです。 エラー処理はバイトあたり0.2サイクルに含まれていることに注意する必要があります。デコーダは入力データをデコードしてチェックする必要があります(たとえば、無効な文字が見つかった場合、デコードはキャンセルされます)。



私たちの研究用のコードは利用可能ですので、結果を再現することができます。 私たちの記事はarXivで公開され、ACM TransactionsのWebバージョンでの公開が許可されています。



私の知る限り、私たちの良い結果はKlomp base64ライブラリに統合されています



追加資料:



Wojciech Mula、Daniel Lemer、「 AVX2命令を使用したBase64エンコードおよびデコードの高速化 」、ACM Transactions Webバージョン(近日公開予定)



All Articles