DEIM Forum 2019 G4-1

Scope-aware Code Completion with Discriminative Modeling
Sheng HU† , Chuan XIAO†† , and Yoshiharu ISHIKAWA†† Graduate School of Informatics, Nagoya University
Furo-cho, Chikusa-ku, Nagoya, 464–8601 Japan†† Institute for Advanced Research, Nagoya University
Furo-cho, Chikusa-ku, Nagoya, 464–8601 Japan
E-mail: †hu@db.ss.is.nagoya-u.ac.jp, ††chuanx@nagoya-u.ac.jp, †††ishikawa@i.nagoya-u.ac.jp
Abstract Code completion is a traditional popular feature for API access in integrated development environments(IDEs). It not only frees programmers from remembering specific details about an API but also saves keystrokes
and corrects typographical errors. Existing methods for code completion usually suggest APIs based on statistics
in code bases described by language models. However, they neglect the fact that the user’s input is also very usefulfor ranking, as the underlying patterns can be used to improve the accuracy of predictions of intended APIs. In thispaper, we propose a novel method to improve the quality of code completion by incorporating the users’ acronym–
like input conventions and the APIs’ scope context into a discriminative model. The users’ input conventions arelearned using a logistic regression model by extracting features from collected training data. The weights in thediscriminative model are learned using a support vector machine (SVM). To improve the real-time eﬃciency ofcode completion, we employ a trie to index and store the scope context information. An eﬃcient top-k algorithm
is developed. Experiments show that our proposed method outperforms the baseline methods in terms of botheﬀectiveness and eﬃciency.
Key words Code completion, discriminative model, top-k ranking

1 Introduction
Code completion is a very useful feature for programmers,
especially beginners, when they input long API names in integrated development environments (IDEs). It aims to help
formulate accurate predictions for users’ intended input APIs
to save keystrokes and avoid typographical errors. This feature becomes popular in prevalent IDEs for the following

Figure 1 Code completion for acronym-like input“SwingUtilities” and “SwingWorker”.

three reasons: First, according to the receiver object type,

We call the above problem setting code completion forcode completion can provide meaningful API method calls

prefix-like input. It receives a prefix-like input and returns

appearing in this object’s definition, hence avoiding low-levela candidate API if the method name begins with the given

incorrect API invocations. Second, if developers are not fa-

prefix. Such setting is adopted in [11]. However, there ismiliar with the APIs that should be called in their current

a major drawback of such a problem setting which makes

context, code completion is able to present all possible com-it unpractical in some cases: when the candidate API set

pletions in a pop-up window, providing an overall view andbecomes larger, completion becomes less eﬀective, especially

documentation to help beginners to learn programming pat-when some prefixes are found to be shared by many API

terns. Third, with code completion, developers are encour-

names. E.g., more than a hundred methods in JButton, aaged to use longer and more descriptive method names toclass of Java, begin with the prefix “get”. To narrow down

improve code readability. We show an example of code com-the candidate list, a user has to additionally type a longer

pletion in Example 1.

prefix which significantly compromises the benefit of code

［Example 1］ In Fig. 1, a user wants to input an API

completion.

name “SwingUtilities”. He types the first few characters

To solve this problem, we need to find the intended API

such as “swin”, and then the system automatically suggests

name by requiring a short input from the user to reduce theas the co-occurrences of APIs in a scope, is also found to be ahelpful feature to improve the prediction accuracy. The reason is that there are many fixed API pattern flows in a scopefor a specific utility. E.g., Fig. 2 shows a typical API invoking
pattern flow for graphics processing, while Fig. 3 shows another case for video processing. Detecting such scope utility
Figure 2 Scope for graphics utility

type can obviously improve the prediction accuracy whena new API invoking statement is inserted into the current
scope.
To integrate diﬀerent features, we propose a discriminative model which can assign diﬀerent weights for each feature
to achieve more accurate performance. This discriminative

Figure 3 Scope for video utility

model consists of three features:

1) the API usage counts

typing eﬀorts. In this paper, we adopt an acronym-like in-collected from the training corpus to reflect the popularity

put paradigm instead of the prefix-like one. An illustratingof each API, 2) the transformation probability that a user’s

example is shown below.

input is transformed into the intended API, and 3) the scope［Example 2］ In Fig. 1, suppose the user types in char-context information represented by co-occurrence counts ofacters such as “swu”.

Then the system adopting

APIs, for which a transformation model is learned by logis-

acronym-like matching paradigm suggests “SwingUtilities”,

tic regression. The above features are combined linearly in“SetWrapGuidePainted”, “ShowCurrentItem” and “Show-the discriminative model for the overall prediction, and their（注 1）

FullPath”.

weights are learned by a support vector machine (SVM).

We call such a problem setting code completion for

In addition to the prediction accuracy, we address the eﬃ-

acronym-like input. It receives an acronym-like input andciency challenges when computing the top-k completions us-

returns a candidate API if the method name contains all theing our discriminative model. Specifically, we develop a can-characters of the input in a subsequence matching way（注 2）.

didate ranker framework to firstly generate the most possible

Existing solutions to code completion focus on using neural

k candidates and then use the ranker to re-rank the top-k

language models [6,7] or statistical language models [1,8–10]

results. We use a trie index to eﬃciently generate the pos-learned from a large code base by modeling it into a natural

sible candidates and then use inverted lists located on thelanguage processing problem. However, they fail to utilize

trie’s leaf nodes to store the scope context information for

the user’s input to narrow down the candidate list by proper

fast co-occurrence lookups.

relevance ranking. We argue that the acronym-like input

Experiments are conducted with a large-scale training

from users will remarkably improve the completion accuracy

dataset collected from GitHub and a test set which covers

when the underlying input patterns are taken into consider-

12 popular Java projects. The results demonstrate the eﬀec-

ation. Intuitively, an acronym-like input from a user will betiveness of our approach: it outperforms the baseline meth-definitely aﬀected by some acronym patterns due to humanods by up to 7.3% on top-1 accuracy. The experiments on

typing behavior. Take an example in Fig. 1. A user’s input

eﬃciency show that our approach is faster than the baseline“swut” has a higher probability to match “SwingUtilities”

methods by up to 31 times.

than to match “ShowFullPath”, because the acronym forTo the best of our knowledge, this is the first work thatthe latter is hardly to be “swut” in common practice. In

focuses on improving ranking performance on the problem oforder to take advantage of the underlying patterns of hu-

code completion by utilizing the user’s input. We also noteman typing behavior, a transformation model needs to bethat our method is orthogonal with the existing code sugges-

learned for the purpose of providing high-quality candidates.

tion methods [1, 8–10] because it can independently work as

In this work, we use a machine learning technique to learna standalone module after language model-based code sug-

the patterns to obtain a transformation model.

gestions.

The scope context information [1,8–10], which is described（注 1）：Without losing generality, we capitalize all the first characters

Our main contributions are summarized as follows.
•

acronym-like input.

of API names for the ease of illustration.
（注 2）：In our practical setting without losing generality, we assume

that the first characters of an input and an API candidate must be
exactly matched.

We propose a novel method for code completion using•

We propose a discriminative model that combines API
counts, transformation probability, and scope context

trained by a logistic regression model.
（ 3 ） Search for API candidates from the trie by matching

the user’s input in a subsequence matching way. The
previous s lines of context from current code position
are taken as the scope context information. Then weuse a traditional noisy channel model to roughly rank
and output a top-k list as the candidate pool. Finally,
we use the trained SVM to re-rank the top-k list to obtain an ultimate result list.
We first introduce a traditional noisy channel model and thenFigure 4 Overview of the process

information for accurate code completion.

give the definition of our discriminative model.
2 1 Noisy Channel Model
Noisy channel model is widely used in string transforma-••

We develop an eﬃcient algorithm to compute top-k can-tion tasks, especially for spelling correction. Given an input

didates from a trie index.

Q = q1 · · · q|Q| , we want to find the best transformed string

Extensive experiments show the performance of both ef-

C = c1 · · · c|C| among all candidates that match the input:

fectiveness and eﬃciency.

C∗ = arg max P (C|Q)(1)

C

The rest of our paper is organized as follows: Section 2
presents the details of our discriminative model. Section 3
shows the index structure and candidate ranker framework.

By applying Bayes’ Rule and dropping the constant denominator, we haveC∗ = arg max P (Q|C)P (C)Section 4 reports the experimental results. Section 5 surveys
related work. Section 6 concludes the paper.

2 A Ranker-based ModelIn this section, we propose a discriminative model to rank
the API candidates. The basic idea of our model is to combine three main features with a proper weighting for moreaccurate predictions. To account for eﬃciency challenges, we
adopt a ranker-based model which consists of a candidate
generator and an SVM-based ranker. First, the candidate
generator uses a traditional noisy channel model to roughly
pick up the most possible top-k API completions. Then,a carefully tuned SVM-based ranker will re-rank the top-k
completions again and finally output a re-ranked completion
list. An overview is showed in Fig. 4. Our process includes
three steps:（ 1 ） API names are indexed using a trie, with correspond-(2)C

where the transformation model P (Q|C) models the transformation probability from C to Q, and the language model
P (C) models how likely C is the intended input. One problem with the noisy channel model is that there is no weighting
for the two kinds of probabilities, and because they are often estimated from diverse sources, suboptimal performancemight be incurred with regarding to diversity of the sources.
Moreover, noisy channel model cannot utilize additional useful features (E.g., scope context information) which becomesa severe limitation in practice.
As our subsequence matching paradigm can be seen as a
generalized case for string transformation, we can use noisy
channel model directly to model our problem.
The language model P (C) can be trained by simply counting the frequency of the API names in the code base, in linewith many previous works [1, 4].

ing scope context information collected from our large

The transformation probability P (Q|C) is learned using

training corpus. Each scope is assigned with a uniquea logistic regression model and the training details are thescope ID and each API has a list of scope IDs such thatsame with the work [2]. The logistic regression model isthis API appears in these scopes. Such lists of scope IDs

shown below:

are linked with the leaf nodes of our trie index for fast

P (Q|C) = g(β0 + β1 · Sim1 (Q, C) + · · · + β6 · Sim6 (Q, C))access.
（ 2 ） An SVM is trained using three features, which are API

where

g(z) =

1
1 + e−z(3)usage counts collected from our code base, transformation probability and scope co-occurrence counts. The

where βi represents the regression coeﬃcients, Simi (Q, C)

transformation probability describes how likely the in-is the similarity feature showed in Table 1 and g(z) is theput from the user is the completion candidate and islogistic function.

of ⟨ API-candidate, feature-vector, class ⟩ triples. The

Table 1 Transformation model features Sim.
ID Description

class has two values: +1 and –1. +1 will be assigned if

Sim1number of consonant letter matches

Sim2

number of vowel letter matches

Sim3

number of capital letter matches

Sim4

number of letter skips

outputs a value between –1 and +1. Then we can use theseSim5

number of skipping occurs

values to rank the candidates.

Sim6

percentage of letter matches

API-candidate is the intended API, otherwise –1 will be assigned. When a candidate is predicted, the trained SVM

3 Searching Algorithm

2 2 Discriminative Model

Table 2 Example dataset S.

A discriminative model may overcome the shortcomings ofID

StringPopularity

noisy channel model by adding additional features and apply-

AP I1

DrawRect

0.6

ing proper weightings. A general discriminative formulation

AP I2

GetGraphics

0.8

of the problem is of the following form:

AP I3

SetAudioSource

0.2

AP I4

SetCamera

0.1

AP I5

SetColor

0.6

C∗ = arg max[w · F(Q, C)]

(4)

C

AP I6

SetVideoSource

0.1

where F(Q, C) is a vector of features and w is the model

AP I7

SetWrapGuidePainted

0.2

parameter which is a vector of weights. Compared with the

AP I8ShowCurrentItem

0.2

noisy channel model, this discriminative formulation is more

AP I9

ShowFullPath

0.1

general. We can deem the nosiy channel model as a special

AP I10SwingUtilities

0.6

case of the discriminative form where only two features, thelanguage model estimates and the transformation probability

In this section, we show the detailed algorithm and in-are used and uniform weightings are applied. In this work,

dex implementation of the three steps showed in Section 2.

the weightings w are derived by training a SVM showed in

Although there is a straightforward way to generate candi-

Section 2 4.

dates: traverse the trie for all possible matching strings and2 3 Scope-awarenessthen calculate all the probabilities for them and sort them

Scope context information has been proved to be very help-

in descending order. However, the number of all matching

ful in code suggestions, as it can describe which API meth-candidates might be prohibitive. Thus we adopt a ranker-

ods are often invoked before the intended API method isbased method which consists of a candidate generator andcalled. We add the scope context variable in our discrimi-

an SVM-based ranker. The candidate generator is respon-

native model as the scope co-occurrence counts. It describes

sible for only picking up the most possible top-k candidates

how often the candidate API appears with its previous API

and then SVM-based ranker will carefully rank these results

names in the same scope by collecting the statistics of thefor higher accuracy. Moreover, in the generator step, earlylarge training corpus. After adding in this feature, our dis-termination techniques and a threshold-based algorithm arecriminative model can be extended as:

applied to eﬃciently compute top-k candidates.
3 1 Candidate Generator of A TrieC∗ = arg max[w0 + w1 · Flang (Q, C)

The basic index structure of the candidate generator is aC

+ w2 · Ftrans (Q, C)(5)+ w3 · Fscope (Q, C)]trie built on top of all the API names. Trie is a tree structure
where each path from the root to a leaf node corresponds to
a API name. Given an input, we can find its corresponding

where Q is the input, C is the candidate, Flang (Q, C) repre-

node, and traverse all its leaf nodes to obtain the correspond-

sents the unigram language model probability, which is calcu-

ing API candidates. An example API set with popularities

lated by a normalized usage counts, Ftrans (Q, C) represents(normalized usa ge counts) is given in Table 2 and the corre-

the transformation probability from C to Q and Fscope (Q, C)

sponding trie is showed in Fig. 5. The API “SwingUtilities”

represents the scope co-occurrence counts of C and Q.

has a trie node 106. On each leaf node, we store the API

2 4 An SVM-based Ranker
The feature vectors are passed to a support vector machine
employing a simple radial basis function (RBF) kernel withr = 1 after all feature values are already normalized between
0 and 1. We employed Joachim SVMlight [5] implementation.
We train the SVM model on a training set that consists

usage counts in it and link it with an inverted list of theordered scope IDs. We call such inverted list scope inverted
list. With the ordered scope inverted list, we can look up forco-occurrences by simply doing a list intersection operationeﬃciently.

1
D G
2
r
3
a
4
w
5
R
6
e
7
c
8
t
9

sp1

10
e
11
t
12
G
13
r
14
a
15
p
16
h
17
i
18
c
19
s
20

sp1

DatasetS
21eJava Corpus 10,753,168 86,158

A

sp2

a
36
m
37
e
38
r
39
a
40

sp2

C
35

V
o
41
l
42
o
43
r
44

sp2

W
45
i
46
d
47
e
48
o
49
S
50
o
51
u
52
r
53
c
54
e
55

sp2

w

h

22
t
23
24
u
25
d
26
i
27
o
28
S
29
o
30
u
31
r
32
c
33
e
34

56
r
57
a
58
p
59
G
60
u
61
i
62
d
63
e
64
P
65
a
66
i
67
n
68
t
69
e
70
d
71
sp1

Table 3 Dataset statistics
LOCs
Files Total Projects

72
o
73
w
74
C
75
u
76
r
77
r
78
e
79
n
80
t
81
I
82
t
83
e
84
m
85

F
86
u
87
l
88
l
89
P
90
a
91
t
92
h
93

94
i
95
n
96
g
97
U
98
t
99
i
100
l
101
i
102
t
103
i
104
e
105
s
106

Java Test

2,788,955 11,371

1,000
12

In detail, when a user issues an input q, we send the q andprevious scope context line(s) s to the search algorithm. We
first search for s to obtain the scope inverted lists of the API
results. Then we search q according to a subsequence matching manner in the trie. For each matched path in the trie,
we compute the transformation probability by the logistic
function in Equation 3. Then we can use P (C) · P (Q|C) tocompute a upper bound score UB. By using the UB, we cancompute the rough top-k candidates eﬃciently by using apriority queue for early termination. After that, intersection
operations are only done between scope context and top-k
candidates. Feature vectors will be sent to our SVM for a
final ranking.
The time complexity is O(k|s|+N logk), reducing from thenaı̈ve one’s O(O|s| + OlogO), where k is the candidate poolsize, |s| is the context size, i.e., the number of context lines,
N is the number of candidates scanned until the process terminated and O is the number of unique API names.

sp2

sp2

4 Experiments

sp1

Figure 5 Trie with scope inverted lists

In this section, we conducted extensive experiments toTake an example in Fig. 1, for an input “swu” and its scope

evaluate both eﬀectiveness and eﬃciency of our proposedcontext “DrawRect”. One node that matches “swu” is node

method against baseline methods.

98. One node that matches “DrawRect” is node 9. Node 9

4 1 Experiment Setup

is already a leaf node and node 98 has an only descendant

Two datasets are collected for model training and testingleaf node 106. Both nodes have scope inverted lists of ⟨ sp1 ⟩and ⟨ sp1 ⟩, respectively. After intersecting these two lists, wetasks.
•

obtain the co-occurrence scope and the co-occurence countfrom all Java projects on GitHub. We sample the large

for “swu” and “DrawRect” is ⟨ sp1 ⟩ and 1, respectively.

corpus into 1,000 projects Java Corpus as a training

3 2 Eﬃcient Ranking Algorithm

set in our evaluations. We use the API usage counts andWe observe that with the increase of the scope context

scope context extracted from this code base.

lines, the co-occurrence computation will need prohibitive
intersection operations for the scope inverted lists of all theJava Corpus（注 3） is a large-scale code base collected•Java Test is a dataset used in [2] collected from 12 pop-

possible candidates. This cost can be unbearable for a real-ular Java projects. We use this dataset as a test set fortime code completion system. To solve this issue, we firstevaluations.

select the most possible candidates by using a noisy channel
model showed in Section 2. Recall that this model needs tocompute a product of P (C) · P (Q|C). P (C) is stored at eachleaf node in the trie, hence we can materialize the maximum
P (C) at each intermediate node for a threshold algorithm(TA). P (Q|C) is computed on-the-fly using a logistic function showed in Section 2. Note that as the logistic function
is a monotonically increasing function, we can also obtain

Table 3 shows the statistics of the two datasets, where LOCs
is the line of codes, Files is the number of files and Total
Projects is the number of projects included.
We only use APIs in Java Development Kit (JDK) as thedictionary to build the trie index. In total 17,116 APIs appearing in JDK 8 are collected to build the trie.
We use the code base of Java Corpus as our corpus anda maximum upper value of P (Q|C) by only computing thelongest prefix matched with the input.

（注 3）：http://groups.inf.ed.ac.uk/cup/javaGithub/use Eclipse’s Java parser to parse the code for scope ex-

Table 4 Accuracy comparison

tractions. We tried diﬀerent scope granularity such as class

Model top-1 top-3 top-5 top-10 MRR

scope, method scope and block scope. Finally we choose touse class scope for the best balance between eﬃciency and

POP

81.0

95.7

97.7

98.7

0.884

NCM

81.8

96.2

97.7

98.7

0.891

SDM

88.3

97.3

98.6

99.0

0.928

accuracy. API usage counts are also extracted from Java
Corpus.
To train the logistic regression model, we extract 5,000 API

studies [3, 7, 8]. We evaluate: (1) top-k accuracy, which in-names, 4,000 from Java Corpus and 1,000 from Java Test.

dicates the fraction of times the correct API appears in the

Then we use these API names to collect 5,000 acronym-like

top-k candidates, where k ∈ 1, 3, 5, 10. (2) Mean Reciprocal⟨input, AP I⟩ pairs. The acronym-like input is collected from

Ranking (MRR), which is calculated as the average recipro-

volunteers in Amazon Mechanical Turk, by telling them tocal of the correct API’s rank in the top-k candidates. MRR

intuitively give an input when they see an original API name.

can give an overall evaluation of the model. The closer to 1

Our transformation model is trained on the complete train-

the MRR value, the better the ranking accuracy.

ing set using logistic regression model showed in Section 2
and well tuned by enough iterations.

We first evaluate the top-k accuracy with the baseline
methods. Table 4 shows the results. The last column shows

To train the SVM model, for each API name in the train-

the comparison of MRR. As seen, SDM achieves higher ac-

ing set, we find an appropriate scope in Java Corpus forcuracy than any other baseline method. At top-1 accuracy,

the API to fit in and extract its previous API names lo-

SDM has the largest improvements of 7.3%, 6.5%, over POP

cated in the scope context. Similarly, for each API in theand NCM, respectively. Along with the increase of k, the ad-test set, we also find an appropriate scope in Java Test

vantage becomes not that obvious because the correct API

and extract its previous API names as context for prediction

will be more easily included in a larger top-k list. Nonethe-purpose. Then we generate the candidates’ feature vectors as

less, SDM still outperforms POP and NCM on all the values of⟨ candidate, input, context ⟩, where candidate represents thek. NCM is better than naı̈ve POP approach, which suggests

candidate API name, input is the user input and context isthat the input from user is useful to predict the intended

the scope context API(s).

API names. However, the observed improvements over POP

The following algorithms are compared.

are very limited due to the lack of weights applied in NCM.
We also observe that, SDM achieves the highest MRR of•

POP is the popularity-based sorting method used in [4].

•NCM is the noisy channel model method described in
Section 2.

0.928, meaning that on average in 10 cases, it can almost
correctly rank the API on top of its list among 9 cases. The
relative improvements on MRR is 3.3% and 1.9% over POP
and NCM, respectively. These experimental results verified•

SDM is our proposed scope-aware ranker-based method

the significant improvements on accuracy of our proposedwith discriminative modeling.

scope-aware discriminative model.

Note that in NCM and SDM, the candidate pool size is set to
50. That is, in SDM, the top-50 results are first selected andthen passed to our SVM for further re-ranking. We have
tried diﬀerent values for the candidate pool size and 50 isproved to well balance the trade-oﬀ between processing timeand accuracy.
In addition, we extract the nearest one line prior to thecurrent calling method as the scope context information in
default for better performance unless other explicit statement is made. The reason is explained in Section 4 2.
The experiments were carried out on a PC with an Intel i5 2.6GHz Processor and 32GB RAM, running Ubuntu
14.04.3. The algorithms were implemented in C++ and in amain memory fashion.
4 2 Evaluation of EﬀectivenessWe adopt the same evaluation metrics used in existingFig. 6 shows an overall comparison for top-k accuracy byvarying k from 1 to 30. We can observe that SDM outperforms other two baseline methods at any k ∈ [1, 30]. The
advantage becomes close in [20,30] because for a large k,even the baseline method can include the correct candidate
easily. Another valuable observation is that when k = 30,
SDM is still higher than POP and NCM, this suggests that
there are some API names especially with low frequency inthe code base can never be retrieved by POP or NCM. As
our SDM can consider the scope context and apply a proper
weighting on it, these rare API names can be easily retrievedin our model.
Varying Context Line Size. Scope context size may
have large impacts on the accuracy of our model. Here, we
explain the scope context size as the number of lines prior tothe current calling method within the same scope. The cooccurrence counts between each context line and current API

SDM

NCM

POP

4 3 Evaluation of Eﬃciency

100
Top-k Accuracy

A practical code completion system must be eﬃcient95

enough to work in real-time to avoid interrupting a developer’s flow of coding. Thus, for eﬃciency, we evaluate the90

overall processing times in Fig. 7. If not clarified, the scope
85

context size and training set will be set to 1 and Train1000 in
default. In Fig. 7, we vary the input length and plot the aver-

80
0

4

8

12

16

20

24

28

32

age runtime of the code completion system as SDM. We alsokFigure 6 Top-k accuracy of diﬀerent approaches

plot the results of the straightforward method mentioned incandidate are summed as the feature co-occurrence counts.

Section 3, denoted by SDM-NoNCM, meaning without theTable 5 shows the results by varying the scope context size

noisy channel model but send all the matched API candi-

from 1 to 5. Interestingly, we can observe that with thedates to our SVM for ranking. We can directly observe that

increase of the context size, the accuracy slightly drops, theSDM is much faster than SDM-NoNCM, because SDM uses

same as the MRR. We examined the test examples and founda noisy channel model to drop hopeless candidates with ex-that summing up co-occurrence counts of multiple previous

treme low probabilities to avoid prohibitive additional com-lines might over-weigh the co-occurrence feature in our model

putations. The maximum speedup is 31 times, at length ofthus lead to inaccurate predictions. This fact reminds us that

1. SDM-NoNCM is very slow due to the numerous matchedexcessive context information might be not beneficial to ac-

API candidates which are needed to be passed to SVM given

curacy but lead to deteriorative performances. There mighta short input while our SDM only keeps the most possible

be a way to take use of the multiple lines of context infor-k API candidates for re-ranking. SDM is around 1 ms formation more properly but such techniques are beyond theall the lengths thus can be applied to Web settings, such as

scope of this paper.

online IDEs. The times begin to decrease when we use alonger input because longer input is more selective thus less

Table 5 Accuracy with diﬀerent context size

candidates are processed for both SDM and SDM-NoNCM.

Context Size top-1 top-3 top-5 top-10 MRR
88.3

97.3

98.6

99.0

SDM

0.928

2

85.5

97.3

98.6

99.0

0.913

3

85.5

97.1

98.6

99.0

0.912

4

85.5

97.1

98.4

99.0

0.912

5

85.5

97.1

98.4

99.0

0.912

Varying Training Set Size. We also want to analyze theimpacts on accuracy by varying the size of our training set.
For our large-scale dataset Java Corpus, we randomly sample the 1,000 projects into two subsets, one with 300 projects
and one with 100 projects, denoted by Train300 and Train100.
Then we evaluate the accuracy by varying these three training sets. We show the results in Table 6. We can obviously see that Train1000 always outperforms Train100 andTrain300. The largest improvements occur at top-1, are 4.8%
and 2.6% over Train100 and Train300, respectively. Train300
is always better than Train100. This verified our intuition
that a larger training set will contribute to better prediction

SDM-NoNCM

2

Processing Time (ms)

1

10

101

100

10-1

1

2

3

4

5

6

7

8

Input Length

Figure 7 Processing time comparison

Varying Context Line Size. The processing times byvarying scope context line size are compared. Fig. 8 shows
the results by varying the context size from 1 to 5. As seen,a large context size might incur considerable overhead thatcauses sensible system delays. Context-5 is almost 3–4 times
slower than Context-1. This suggests that if multiple lines ofcontext information are used, further optimization on processing might be required.
Varying Training Set Size. The processing times by

accuracy.

varying training set size are evaluated. For our large-scale
Table 6 Accuracy of diﬀerent training set size

dataset Java Corpus, we show the results in Fig. 9. The
evaluated training set is the same with that in Table 6.

Datasettop-1 top-3 top-5 top-10 MRR

Train100

83.5

96.1

97.6

98.7

0.898

Train1000 is the slowest, 1.8 and 1.5 times slower thanTrain300

85.7

96.4

98.1

98.7

0.911

Train100 and Train300, at the length of 1 while its corpus

Train1000

88.3

97.3

98.6

99.0

0.928

size is 10 and 3.3 times larger than Train100 and Train300.

Processing Time (ms)Context-1
Context-2
Context-3

Context-4
Context-5

tion using a scope-aware ranker-based discriminative ranking model. We use an acronym-like input setting to avoid

10

the fatal drawback of existing code completion systems. To
improve the accuracy, we utilize API usage counts, transfor1

mation probability and scope context information as the features to pass to our trained SVM as a discriminative model.
To solve the eﬃciency challenge, we adopt a ranker-based

0.1
1

2

3

4

5

6

7

8

Input Length

model to use noisy channel model as a filter to eliminate

Figure 8 Processing time with diﬀerent context size

hopeless candidates. The experimental results have shown

Intuitively, the larger the training corpus, the slower the pro-that our proposed method outperforms the baseline meth-cessing time. This is mainly because larger training corpus

ods in terms of both eﬀectiveness and eﬃciency.

will contain more scope context information such that theacknowledgment

scope inverted list will become longer and slower for lookup
operations. Nonetheless, the growth rate on processing time
is much lower than the corpus size, thus a larger corpus might
be always preferable for better accuracy performance.

Processing Time (ms)Train100
Train300

Train1000

1

0.1
1

2

3

4

5

6

7

8

Input Length

Figure 9 Processing time with diﬀerent training set size

5 Related Work
Code Completion. With the birth of text editors, theresearch on code completion has received much attention in
the past several decades. In one early study, Willis et al. [12]proposed an approach to expand some abbreviations into a
sentence to save input eﬀorts. After this work, Han et al. [2]used a hidden Markov Model learning from a code corpus
to expand ordered abbreviated keywords into a valid code
expression.
Code Suggestion. The code suggestion problem is totry using statistical language models [1] (LMs) to predict
the next code line without any input from users. Nguyen
et al. [10] proposed to use a semantic model to capture thepatterns of source code, by incorporating a local semantic ngram model with a global n-gram topic model. Graph-based
LMs are proposed in [8] to capture graph-based patterns
from source code. Scope and context information has been
proved to greatly improve the accuracy for predictions inthese studies [8,10]. Recent trends feature a boom by applying the Deep Learning Network (DNN) instead of LMs.

6 Conclusion
In this paper, we have studied the problem of code comple-

This work was partly supported by JSPS KAKENHI Grant
Number JP16H01722.
References[1] M. Asaduzzaman, C. K. Roy, K. A. Schneider, and D. Hou.
CSCC: simple, eﬃcient, context sensitive code completion.
In ICSME 2014, Victoria, BC, Canada, September 29 October 3, 2014, pages 71–80, 2014.
[2] S. Han, D. R. Wallace, and R. C. Miller. Code completionof multiple keywords from abbreviated input. ASE, 18(34):363–398, 2011.
[3] V. J. Hellendoorn and P. T. Devanbu. Are deep neuralnetworks the best choice for modeling source code? In
ESEC/FSE 2017, Paderborn, Germany, September 4-8,
2017, pages 763–773, 2017.
[4] D. Hou and D. M. Pletcher. An evaluation of the strategies of sorting, filtering, and grouping API methods forcode completion. In ICSM 2011, Williamsburg, VA, USA,
September 25-30, 2011, pages 233–242, 2011.
[5] T. Joachims. Making large-scale SVM learning practical. In
B. Schölkopf, C. Burges, and A. Smola, editors, Advancesin Kernel Methods - Support Vector Learning, chapter 11,
pages 169–184. MIT Press, Cambridge, MA, 1999.
[6] J. Li, Y. Wang, M. R. Lyu, and I. King. Code completion with neural attention and pointer networks. In IJCAI
2018, July 13-19, 2018, Stockholm, Sweden., pages 4159–
4165, 2018.
[7] A. T. Nguyen, T. D. Nguyen, H. D. Phan, and T. N.
Nguyen. A deep neural network language model with contexts for source code. In SANER 2018, Campobasso, Italy,
March 20-23, 2018, pages 323–334, 2018.
[8] A. T. Nguyen and T. N. Nguyen. Graph-based statisticallanguage model for code. In ICSE 2015, Florence, Italy,
May 16-24, 2015, Volume 1, pages 858–868, 2015.
[9] A. T. Nguyen, T. T. Nguyen, H. A. Nguyen, A. Tamrawi,
H. V. Nguyen, J. M. Al-Kofahi, and T. N. Nguyen. Graphbased pattern-oriented, context-sensitive source code completion. In ICSE 2012, June 2-9, 2012, Zurich, Switzerland,
pages 69–79, 2012.
[10] T. T. Nguyen, A. T. Nguyen, H. A. Nguyen, and T. N.
Nguyen. A statistical semantic language model for sourcecode. In ESEC/FSE’13, Saint Petersburg, Russian Federation, August 18-26, 2013, pages 532–542, 2013.
[11] R. Robbes and M. Lanza. How program history can improve code completion. In ASE 2008, 15-19 September
2008, L’Aquila, Italy, pages 317–326, 2008.
[12] T. Willis, H. Pain, S. Trewin, and S. Clark. Informing flexible abbreviation expansion for users with motor disabilities.
In ICCHP 2002, Linz, Austria, July 15-20, Proceedings,
pages 251–258, 2002.