Currently the Department Control is not so fast because it uses the database, it doesn't use any search engine and reads tables like taxonomy statistics.
The Departments Control supports "Caching" which means that if it is put on a page with output cache enabled it should not take so long.
If we don't count the caching, if you see with SQL profiler what sql queries are slowest (there should be some queries over TaxonomyStatistic (sf_taxonomy_statistic)
for example) and you may try to optimize them by adding indexes. Currently there are no indexes on that table (except the PK) so adding indexes based on the most time consuming queries will help.
I will add an improvement request for adding index(s) on TaxonomyStatistics. If you manually add indexes to sf_taxonomy_statistic please do not forget to run manual re-indexing after that in case of Microsoft SQL server is used.
I can also advice you to set the ShowEmptyItems property to TRUE which will help by skipping several COUNT queries.
This is all which is currently possible to be made for performance optimizations of the departments control (if we don't count of course replacing the DepartmentControl implementation class to not use an sql database but some third party indexing engine.)
Do you want to have your say in the Sitefinity development roadmap? Do you want to know when a feature you requested is added or when a bug fixed? Explore the Telerik Public Issue Tracking
system and vote to affect the priority of the items