lightdm startup extremely slow when lots of users on system

[Sven Mueller]

With lots of users on the system (>100k users in this case, after filtering those with blacklisted shell or too low UID), lightdm is extremely slow while starting. This seems to be because of this loop, that is run after each single user that was read in:

        /* Update existing users if have them */
        for (link = priv->users; link; link = link->next)
        {
            LightDMUser *info = link->data;
            if (strcmp (lightdm_user_get_name (info), lightdm_user_get_name (user)) == 0)
            {
                if (update_passwd_user (info, lightdm_user_get_real_name (user), lightdm_user_get_home_dir
ectory (user), lightdm_user_get_image (user)))
                    changed_users = g_list_insert_sorted (changed_users, info, compare_user);
                g_object_unref (user);
                user = info;
                break;
            }
        }

With 100k users, this means this loop is executed 100.000 times, with an average of 50.000 iterations, making it 5 billion iterations in total. This is probably the main reason why lightdm takes over a minute to start on the machine in question, while it takes nearly no time (i.e at most 2-3 seconds) to start it on my laptop which only has a handful of valid users.

I personally think the user list (a linked list) should be switched to a hash or tree.

Found in version 1.2.1 (current package from Precise and Precise-Updates: 1.2.1-0ubuntu1 and 1.2.1-0ubuntu1.1).