<commit_before><commit_msg>Create opt-for-haskell-fusion-opt.md (#940)<commit_after>Abstract

It is well known that for routing and switching in 802.11ac wireless network, functional programming is not as useful as usual, since cache miss in routers and switchers will cause severe performance breakdown[1] while functional (immutable) data structures directly affect cache utilization[2]. Several methods[3][4][5] have been invented to improve the performance of functional data structures, but there are still room for optimizations[6]. This paper elaborates a method for optimizing functional data structure cache utilization named "fusion optimization predicating", which allows language runtime to predict further fusion optimizations on thunks, thus load instructions and data ahead of time.

1. Introduction

Over the last several decades CPU speeds have increased dramatically while memory access times have only improved slowly[2]. This trend is likely to continue in the future and it will cause more and more applications to become memory-bound, especially when a server is configured with a large memory with which disk access can be safely ignored due to operating system caching. CPU caching greatly reduced the gap between main memory and CPU by introducing a medium layer, this method have been used for about twenty years since the invention of Intel 80386. However, functional programming in routers and switchers can hardly benefit from CPU caching since fusion optimization, which is a way for lessening memory consumption of thunks in several lazy-evaluation strategied functional languages, can cause severe damage to CPU caching machanism. When a functional language runtime is about to perform fusion, CPU microcodes always fail to do branch prediction. Several CPU side algorithms have been invented to help CPU correctly predicate branch to execute. The most famous one, proposed by <NAME>, was based on deep learning and mainly focus on the recognition of fusion optimization[4]. There are also several "flush less"[3] or "reuse more"[5][6] algorithms. However, CPU can only make limited assumptions on the program being executed on it, which limited the means CPU can use. Our algorithm chooses a different direction: making fusion optimizations more effective, process a batch of fusions at once, and reduce the occurance of fusion optimizations.

2. Background

Fusion optimization is widely considered harmful to CPU caching machanism due to it always mutates status of registers, interrupts control flows and makes branch predicating invalid. A traditional fusion optimization has the following performance[7]:

{'fraction_non_alphanumeric': 0.032917139614074914, 'fraction_numerical': 0.01021566401816118, 'mean_word_length': 5.4487804878048784, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '944341', 'n_tokens_mistral': 555, 'n_tokens_neox': 525, 'n_words': 380}