(Eu queria escrever isso como um comentário, mas ficou muito tempo ... e eu gosto de screenshots)
Eu achei o diálogo de execução do XFCE muito superior ao do GNOME. Está disponível no pacote xfce4-utils e o binário é chamado xfrun4
. Eu atribuí um atalho de teclado, Alt + F2, substituindo o padrão do GNOME.
A razão pela qual vai ser muito mais rápido é porque ele não faz a conclusão do bash (ou qualquer que seja o uso do GNOME). Apenas verifica seu próprio histórico (que será bem menor).