Optimize the speed of [search] applications

This article consistently discusses various aspects of improving application performance using the example of a developed search engine application for the Android mobile operating system. If the search engine itself can be useful to various users with a large number of programs, then the article will be of interest primarily to developers (not only android developers). And for all readers, regardless of the platform, at the end of the survey attached " What is first and foremost important for me in a mobile application? "


I welcome you, readers of Habr,

I'll start with a little background - with a description of the problem, and then I’ll continue with how I solved the problem.
')
I, as the proud owner of an android phone, am very pleased with the openness of the system and the ability to put there many applications from both different markets and downloaded from somewhere. On average, there are about 150 applications on my good old Galaxy Note, most of which I use periodically.

With the feeling that the more application cows there are, the more milk benefits from my phone, I noticed that I spend a lot of time paging from screen to screen in search of the icon of the desired application. When cows have few programs, then they are easier to find. They can be put on the home screen or spread by daddies. All this is good and convenient if you use 20-30 applications.
But since I belong to the category of heavy users, I began to look for a quick method of searching for applications.

The requirements for solving a problem are quite simple:
the search should be fast and resource-saving (processor, battery), and everything should happen automatically - I don’t want to install, sort or push anything into folders.

To solve this problem, I started searching for an application for quick search and found several applications in the market for searching and launching applications, but they all had various disadvantages, especially in the search, so I had to be content with the standard android search from Google. He was of course slow, but he was looking well and found what he needed.

At some point after the update to Android 4.1, Google Now came to replace the search, which suddenly stopped working without connecting to the Internet (maybe just me?), Began to gnaw on the battery terribly and offer me trips where I’m not going to go at all. Only now look for the program completely stopped.

Thinking: “Ehh, google, what became of you - the managers to collect personal data replaced the developers” began to look for other programs, but apart from the continuous launchers that need to be customized, I did not find anything (I didn’t search for the wrong words).

Well, since there is nothing, what can I do, I can dig a trench on the keys in the IDE, I think there is a business there for a day, I will make a convenient program for myself - as they say: “It’s better to lose a day, and then fly in an hour” .

The main condition: finding the result should be fast.

I will talk about this in this article (so that it is not boring, the text will be periodically accompanied by a code)
Everything that is written is not new, but rather is a selection of what to look for to improve the performance of programs.
As a visual example, a specific program written in Java for the Android OS is given, but these aspects apply to other environments.



The main action in the desired program is to search for other programs by the entered keyword, i.e. search for other application metadata.
Querying this data from the operating system is not a big problem:

Intent i=new Intent(Intent.ACTION_MAIN, null); i.addCategory(Intent.CATEGORY_LAUNCHER); final List<ResolveInfo> apps = context.getPackageManager().queryIntentActivities(i, 0); 

0. The simplest solution is linear search.

In fact, we run through the list and show all that we have to the user.
And here it is - tree braking. With 150 programs such a search takes a few seconds.
Well, this is logical when O (n) is complex, which in the worst case means 150 comparison operations before being found, but this is not good, I would like O (log (n)). As we all know, when searching for such complexity we are given trees (I will not go into what trees give what complexity when searching, but a good table is here ).
Conclusion: Do not use linear search if you have many items.

1. Quick solution - search using trees

a) Most trees work when searching for information with complexity O (log (n)), i.e. for 150 elements, on average, slightly more than two operations are needed. This improvement almost 50-70 times suited me (and if you consider that the search takes place in several fields, the improvement is thousands of times).
Conclusion: if you want to search for something in unstructured information - save time or still structure the information.

b) Where do you get this tree? First you need to build a tree from the available information - this process is called indexing. Here lies a big BUT: this very indexing can take from O (n log (n)) to, oh God, O (n ^ 2).
Conclusion: do not forget that with “It is better to lose a day, and then fly in an hour”, you still lose a day at first, so index only if you have a lot of data, you often look for data and rarely change data (the same applies to data in hash tables and sorted lists).

c) From purely masochistic motives, I certainly experimented a couple of days with the implementation of my own indexing, getting the desired tree with speeding up the search process. True, after testing my own tree, I decided to compare it in speed with the indices from Sqlite - the results were far from in favor of my implementation (I think Java is slow in comparison with the implementation of Sqlite in C). I decided to use Sqlite after all.
Conclusion: do not reinvent the wheel - use ready-made quick solutions for indexes, written in native languages.

2. Data output from the database

The next serious loss of time occurs during data output from the database.
The fact is that trees / indexes only contain pointers to the necessary data, which now need to be read and transported to where they were requested from. At this place, it will only be possible to optimize by reducing the amount of data at the output, which specifically means that

 SELECT * FROM data 

- This is an evil that consumes system resources (memory and processor cycles for allocation and garbage collection).
Conclusion: specify the columns that you need specifically, otherwise the data you do not need will block resources.

3. Memory or speed

Decide what is more important to you in the program: low CPU consumption or low memory consumption. The latter takes precedence in the rare cases where the memory is simply not enough. If the program is constantly running in the background, then both factors are important. In most cases, the first factor is more important: the less operations your program performs, the faster it works, which means there are more clocks left for other applications. If the already requested / calculated / found information does not change and needs to be reused, it is better to cache it in order not to use the processor a second time to calculate what has already been calculated.



Now let's look at how exactly in our case such caching helps to improve performance:

a) with the expected reapplication of data obtained in certain parts of the code (cycles, functions), it is more advantageous to save the result obtained. For example:

 static int[] a=new int[1000]; for(int i=0;i<a.length;i++){ ... } // 1. for(int i=0,len=a.length;i<len;i++){ ... } // 2. for(int i:a){ ... } // 3. 

If we compare options 1 and 2, then option 2 is faster, because it saves a couple of operations to extract the length value from object a, although in this case it is not critical because of direct access to the variable. If this would be the length() function, then everything would be much sadder in option 1 (in the interpreted languages ​​it is just sad, in the compiled languages ​​it depends on the compiler: it can see and optimize this sadness, or maybe not). I would call the first version of the taboo.

In the documentation for android, Google insistently asks to use option 3, which makes me think that int[] implemented as a List, and not as Array, so the use of an iterator offers speed advantages.
Conclusion: depending on the programming language, you should look into the documentation and find out which method is recommended. For Array, usually option 2, for List, usually option 3.

Further optimizations depend on the programming language, but it is worth remembering that every use of functions means working with a stack (of course, excluding the snyh inline functions). I will not give other micro-optimizations in this place (maybe a topic for another article).
Such micro-optimization seems to be unnecessary, but if you think that with large numbers of repeated executions, this section sometimes slows down 1000 times due to the wrong code, then the improvement is noticeable.

b) in our case, in addition to textual information about applications, the application icon is also displayed.
Usually, it is requested through the loadIcon() function, but this request searches for an icon in application packages, which takes longer than requesting it from the database. Therefore, during indexing, we will also add icons to the Sqlite database. Again, there is a choice between speed and memory consumption: faster execution requires caching and is characterized by additional memory consumption.
Conclusion: caching gives advantages not only in micro-optimization, but also in macro-optimization

4. Graphic shell

One side of the coin is the search for information, the other is what is happening at this time in the graphical shell.
User interaction does not directly affect the speed of the task, but gives him the feeling of whether the program “slows down” or “flies”. First of all, this feeling is caused by the program's reaction to the user's actions. That is, the program should take place on the model:

  click -> change shell -> start a long operation -> get results -> change shell 

instead

  click -> start a long operation -> get results -> change shell 

During the launch of a lengthy operation and receiving results, the shell should not hang, but remain animated to show the user the progress of the action, otherwise you may feel that the program is frozen.

a) Separating a lengthy search operation from the thread in which the graphical shell operates.
Modern processors contain several cores and processing parallel tasks for them is easy.
The allocation to a separate thread, depending on the system, can occur in various ways, the simplest is the use of asynchronous functions (which often have the Async ending in the title). If the function is its own, then it can be parallelized in various ways, in android for example through AsyncTask, Handler or even Timer.

Using AsyncTask looks like this:

 public class Run extends AsyncTask<Context, Integer, Boolean> { @Override protected Boolean doInBackground(Context... arg0) { ... } @Override protected void onPostExecute(Boolean result) { super.onPostExecute(result); // do something or catch by listener } } Run r=new Run();r.execute(this); 

The use of Handler is simpler, but also smaller:

 private final Handler hRefresh = new Handler(); private final Runnable runRefreshData = new Runnable() { @Override public void run() { ... } }; hRefresh.post(runRefreshData); // or hRefresh.postDelayed(runRefreshData,100); 

Timer and standard Java Thread will not be considered here.

b) optionally, using animation of the graphical shell, hide delays caused by searching for information in the background process (if such a process lasts no longer than 1 second). For example, to hide the process of recording a photo taken in memory, a second animation is displayed on the screen.

c) longer processes will require a wait animation or a progress indicator (for example, during indexing). The most important thing in this case, again, is that the action in the graphical shell does not stop.

Conclusion: the graphical shell gives the user the feeling that everything works quickly, even if the processing takes some time

5. Application logic

It is very important to clearly represent the logic of the program - in which place speed is important:

• if we want to load some information into memory so that it can be used quickly, then it will take time to load - this option can be seen in games that turn on the welcome screen after the start, while loading data into memory.
• In our case, it is important that the program starts, if not instantly, but in just a couple of seconds, and of course the quick search itself, which we have already discussed. For a quick start of the program, you need to come up with a strategy to save load time.

a) Download strategy
To optimize the launch time of the application, you must first find out what this time is spent on.
There are so-called profilers in various SDKs in order to get visual results of the time spent.




Those. In our case, both in OnCreate and OnResume, more than 80% of the time is occupied by loading, counting and drawing graphic elements. The more of them and the more complicated their structure and location, the more it will be necessary to recalculate the coordinates on the screen. Especially the use of an adaptive design with the width / height specified in android:weight="" requires increased costs during the construction of graphics. This problem can be solved by using different markup files for different screen sizes, instead of one that adapts. This will certainly increase the size of the final .apk file, but at the same time will increase the speed of the launch of the application.
I repent: this moment is not yet fully satisfied, but it is firmly fixed in the plan of action

Another aspect is the hidden elements of the shell, which will be shown to the user only under certain conditions. To save time when loading such items in the android uses ViewStub . So, for example, in FAppSter you can switch between different keyboards, as well as between the grid and the list. Everything that may not be needed at the moment, we pack in the markup file in ViewStub:

 <ViewStub android:id="@+id/stub_lv_sugg" android:inflatedId="@+id/lv_sugg" android:layout="@layout/a_main_lv_sugg" android:layout_width="wrap_content" android:layout_height="wrap_content"/> 

and in the program code we use instead of lvSugg=(ListView)findViewById(R.id.lv_sugg);

 if (lvSugg == null) { lvSugg = (ListView) ((ViewStub) findViewById(R.id.stub_lv_sugg)).inflate(); } 

Conclusion: with complex graphical shells, a lot of time when you start the android application is spent on downloading graphic elements, which should be optimized

b) The logic of using the program
In different applications, this logic is different, but for the particular example of FAppSter, the main goal is to reduce the time spent by the desired program. Significant reduction of this time compared with the same standard search line, achieved due to the following conclusions:

• If you enter the full name and then search for the result, the input process itself takes a long time and is prone to errors
• If you use the autocomplete drop-down auto list as you type, the number of input errors decreases and the speed of finding increases.
• If you show the results as you type, sorting them by priority, the probability of finding the target more quickly increases.
• If you replace the standard keyboard and reduce the number of buttons to Latin, then the probability of hitting the wrong button decreases
• If you use the principle of the navigation system and deactivate the buttons as you type, then the probability of errors decreases
• If you combine the buttons in the keyboard, thereby reducing it, then the probability of hitting the wrong key decreases (like T9)
• If you search for information about the program not only in the title, but also in other metadata, then the probability of finding a program without knowing the name increases
• If you translate Russian names with the help of transliteration, then you can also search for names in Russian.
• If you allow users to manually add keywords to the programs, you can personalize the search

This is something that has already been implemented.
The program is made for yourself, so free and without advertising - download who needs it. You can also distribute the APK.
If someone has ideas for improvement - write in English on the official page .
Or write in Russian to VKontakte group .

In fact, I and myself still have a lot of ideas on how to improve the search, but unfortunately there is still not enough free time, you still have to work for money for your uncle. So do not wait for instant implementation of wishes, but whenever possible I add wishes and answer questions ;)

Conclusion

The speed of the application depends on many factors that depend on the language and programming environment. In this article, I pointed out some factors and solutions to problems, well, I also showed with an example what you should pay attention to.

Finally, a small survey from the public. I often receive requests to add to the blackjack program, all sorts of buns and designs. Often I doubt what to add and what not to. Therefore, at the end of a small survey, what is personally important for you personally in the mobile application? Thanks for attention