I've made some investigation on messages searching. It was slow and memory expensive. I've found that we can use SORT on servers with that capability (r2046). Also searching with many criterias can be done in one command (r2044). So, in numbers my changes looks as follow:
Searching in forder with 8200 messages, pagesize = 100.
Now - Time: 0.8 sec., Mem: 7.2 MB Before - Time: 0.8 sec., Mem: 8.2 MB 2. Search for "aa" string in body, returns 2060 messages: Now - Time: 2.1 sec., Mem: 8.6 MB Before - Time: 5.5 sec., Mem: 21 MB 3. Search for "a" string in subject and from headers, returns 6090 messages: Now - Time: 1.1 sec., Mem: 11 MB Before - Time: 11.8 sec., Mem: 46 MB
So, it looks cool, but I'm not sure that all IMAP servers are supporting searching with SORT, so please do some tests.
p.s. For IMAP servers without SORT capability we need still some work to do. See my comment (search for "TODO") in r2046.