Why (actually) does it take me so long to make 1000 cubes?
I followed the code from bpy.data.objects.new and will put this here.

Call Hierarchy

rna_Main_objects_new               /* called by python - bpy.data.objects.new */
    BKE_object_add_only_object     /* set default values for the object */
        BKE_libblock_alloc         /* allocate memory for the object */
            new_id                 /* name validation - fallback, not \0, utf8 */
                check_for_dupid    /* check for collisions and find new name*/
                    is_dupid       /* linear search for duplicate name */
                id_sort_by_name    /* sort list */


Links


rna_Main_objects_new
BKE_object_add_only_object
BKE_libblock_alloc
new_id
check_for_dupid
id_sort_by_name


Condensed body of new_id

bool new_id(ListBase *lb, ID *id, const char *tname)
{
    bool result;
    char name[MAX_ID_NAME - 2];

    BLI_strncpy(name, tname, sizeof(name));

    result = check_for_dupid(lb, id, name);
    strcpy(id-&gt;name + 2, name);

    /* however all data in blender should be sorted, not just duplicate names
     * sorting should not hurt, but noting just incase it alters the way other
     * functions work, so sort every time */

    id_sort_by_name(lb, id);

    return result;
}


Body of is_dupid called in check_for_dupid

static ID *is_dupid(ListBase *lb, ID *id, const char *name)
{
    ID *idtest = NULL;

    for (idtest = lb-&gt;first; idtest; idtest = idtest-&gt;next) {
        /* if idtest is not a lib */ 
        if (id != idtest &amp;&amp; idtest-&gt;lib == NULL) {
            /* do not test alphabetic! */
            /* optimized */
            if (idtest-&gt;name[2] == name[0]) {
                /* STREQ - macro for strcmp */
                if (STREQ(name, idtest-&gt;name + 2)) break;
            }
        }
    }

    return idtest;
}


Body of id_sort_by_name

void id_sort_by_name(ListBase *lb, ID *id)
{
    ID *idtest;

    /* insert alphabetically */
    if (lb-&gt;first != lb-&gt;last) {
        BLI_remlink(lb, id);

        idtest = lb-&gt;first;
        while (idtest) {
            if (BLI_strcasecmp(idtest-&gt;name, id-&gt;name) &gt; 0 || 
               (idtest-&gt;lib &amp;&amp; !id-&gt;lib)) {
                BLI_insertlinkbefore(lb, idtest, id);
                break;
            }
            idtest = idtest-&gt;next;
        }
        /* as last */
        if (idtest == NULL) {
            BLI_addtail(lb, id);
        }
    }
}


So indeed blender checks for duplicates and furthermore removes the id from the list again and inserts it alphabetically. 

You can't even trick it by choosing names in the right order C, B, A because is_dupid will search the full list regardless. 

Though if you specify a non colliding name it exits check_for_dupid early and does not have to find a name on its own.

Additionally as others have mentioned you should not use operators unless you have to and only need to create the mesh once.