Accelerating Code Search with Deep Hashing and Code Classification (2022)

Abstract: Code search is to search reusable code snippets from source code corpus based on natural languages queries. Deep learning-based methods on code search have shown promising results. However, previous methods focus on retrieval accuracy, but lacked attention to the efficiency of the retrieval process. We propose a novel method CoSHC to accelerate code search with deep hashing and code classification, aiming to perform efficient code search without sacrificing too much accuracy. To evaluate the effectiveness of CoSHC, we apply our methodon five code search models. Extensive experimental results indicate that compared with previous code search baselines, CoSHC can save more than 90% of retrieval time meanwhile preserving at least 99% of retrieval accuracy.

## introduction code reuse is a common practice during software development process. it improves programming productivity as developers' time and energy can be saved by reusing existing code. according to previous studies @xcite , many developers tend to use natural language to describe the functionality of desired code snippets and search the internet/code corpus for code reuse. many code search approaches @xcite @xcite have been proposed over the years. with the rapid growth of open source code bases and the development of deep learning technology, recently deep learning based approaches have become popular for tackling the code search problem @xcite @xcite . some of these approaches adopt neural network models to encode source code and query descriptions into representation vectors in the same embedding space. the distance between the representation vectors whose original code or description are semantically similar should be small. other approaches @xcite @xcite regard the code search task as a binary classification task, and calculate the probability of code matching the query. in the past, deep learning-based methods focused on retrieval accuracy, but lacked attention to the efficiency of retrieval on large-scale code corpus. however, both types of these deep learning-based approaches directly rank all the source code snippets in the corpus during searching, which will incur a large amount of computational cost. for the approaches that separately encode code and description representation vectors, the similarity of the target query vector with all code representation vectors in the corpus needs to be calculated for every single retrieval. in order to pursue high retrieval accuracy, a high dimension is often set for the representation vectors. for example, in codebert, the dimension of the final representation vector is 768. the similarity calculation between a pair of code and query vectors will take 768 multiplications and 768 additions between two variables with double data type. the total calculation of single linear scan for the whole code corpus containing around 1 million code snippets is extremely large -around 1 billion times of multiplications and additions. as for the approaches adopting binary classification, there is no representation vectors stored in advance and the inference of the target token sequence with all the description token sequences needs to be done in real time for every single retrieval. due to the large number of parameters in the current deep learning models, the computation cost will be significant. hashing is a promising approach to improve the retrieval efficiency and widely adopted in other retrieval tasks such as image-text search and imageimage search. hashing techniques can convert high dimensional vectors into low dimensional binary hash code, which greatly reduce the cost of storage and calculation @xcite . hamming distance between two binary hash code can also be calculated in a very efficient way by running xor instruction on the modern computer architectures @xcite . however, the performance degradation is still not avoidable during the conversion from representation vectors to binary hash codes even the state-of-the-art hashing models are adopted. the tolerance of performance degradation from most users is quite low and many of them are willing to sweep the performance with efficiency. in order to preserve the performance of the original code search models that adopt biencoders for the code-query encoding as much as possible, we integrate deep hashing techniques with code classification, which could mitigate the performance degradation of hashing model in the recall stage by filtering out the irrelevant data. specifically, in this paper, we propose a novel approach coshc (accelerating semantic code search with deep hashing and code classification) for accelerating the retrieval efficiency of deep learning-based code search approaches. coshc firstly clusters the representation vectors into different categories. it then generates binary hash codes for both source code and queries according to the representation vectors from the original models. finally, coshc gives the normalized prediction probability of each category for the given query, and then coshc will decide the number of code candidates for the given query in each category according to the probability. comprehensive experiments have been conducted to validate the performance of the proposed approach. the evaluation results show that coshc can preserve more than 99% performance of most baseline models. we summarize the main contributions of this paper as follows: ## method we propose a general framework to accelerate existing deep code search (dcs) models by decoupling the search procedure into a recall stage and a re-rank stage. our main technical contribution lies in the recall stage. figure 1 illustrates the overall framework of the proposed approach. coshc consists of two components, i.e., offline and online. in offline, we take the code and description embeddings learned in the given dcs model as input, and learn the corresponding hash codes by preserving the relations between the code and description embeddings. in online, we recall a candidate set of code snippets according to the hamming distance between the query and code, and then we use the original dcs model to re-rank the candidates. ## conclusion to accelerate code search, we present coshc, a general method that incorporates deep hashing techniques and code classification. we leverage the twostaged recall and re-rank paradigm in information retrieval field and apply deep hashing techniques for fast recall. furthermore, we propose to utilize a code classification module to retrieve better quality code snippets. experiments on five code search models show that compared with the original code search models, coshc can greatly improve the retrieval efficiency meanwhile preserve almost the same performance.