Index: /trunk/src/wp-admin/includes/class-wp-users-list-table.php
===================================================================
--- /trunk/src/wp-admin/includes/class-wp-users-list-table.php	(revision 41612)
+++ /trunk/src/wp-admin/includes/class-wp-users-list-table.php	(revision 41613)
@@ -167,25 +167,46 @@
 
 		$wp_roles = wp_roles();
+		$count_users = true;
+
+		if ( wp_is_large_user_count() ) {
+			$count_users = false;
+		} elseif ( is_multisite() && wp_is_large_network( 'users' ) ) {
+			$count_users = false;
+		}
 
 		if ( $this->is_site_users ) {
 			$url = 'site-users.php?id=' . $this->site_id;
-			switch_to_blog( $this->site_id );
-			$users_of_blog = count_users( 'time', $this->site_id );
-			restore_current_blog();
+			if ( $count_users ) {
+				switch_to_blog( $this->site_id );
+				$users_of_blog = count_users( 'time', $this->site_id );
+				restore_current_blog();
+			}
 		} else {
 			$url = 'users.php';
-			$users_of_blog = count_users();
-		}
-
-		$total_users = $users_of_blog['total_users'];
-		$avail_roles =& $users_of_blog['avail_roles'];
-		unset($users_of_blog);
+			if ( $count_users ) {
+				$users_of_blog = count_users();
+			}
+		}
+
+		if ( $count_users ) {
+			$total_users = $users_of_blog['total_users'];
+			$avail_roles =& $users_of_blog['avail_roles'];
+			unset($users_of_blog);
+		} else {
+			$avail_roles = array();
+		}
 
 		$class = empty($role) ? ' class="current"' : '';
 		$role_links = array();
-		$role_links['all'] = "<a href='$url'$class>" . sprintf( _nx( 'All <span class="count">(%s)</span>', 'All <span class="count">(%s)</span>', $total_users, 'users' ), number_format_i18n( $total_users ) ) . '</a>';
+
+		if ( $count_users ) {
+			$role_links['all'] = "<a href='$url'$class>" . sprintf( _nx( 'All <span class="count">(%s)</span>', 'All <span class="count">(%s)</span>', $total_users, 'users' ), number_format_i18n( $total_users ) ) . '</a>';
+		} else {
+			$role_links['all'] = "<a href='$url'$class>" . _x( 'All', 'users' ) . '</a>';
+		}
 		foreach ( $wp_roles->get_names() as $this_role => $name ) {
-			if ( !isset($avail_roles[$this_role]) )
+			if ( $count_users && !isset($avail_roles[$this_role]) ) {
 				continue;
+			}
 
 			$class = '';
@@ -196,10 +217,12 @@
 
 			$name = translate_user_role( $name );
-			/* translators: User role name with count */
-			$name = sprintf( __('%1$s <span class="count">(%2$s)</span>'), $name, number_format_i18n( $avail_roles[$this_role] ) );
+			if ( $count_users ) {
+				/* translators: User role name with count */
+				$name = sprintf( __('%1$s <span class="count">(%2$s)</span>'), $name, number_format_i18n( $avail_roles[$this_role] ) );
+			}
 			$role_links[$this_role] = "<a href='" . esc_url( add_query_arg( 'role', $this_role, $url ) ) . "'$class>$name</a>";
 		}
 
-		if ( ! empty( $avail_roles['none' ] ) ) {
+		if ( ! $count_users || ! empty( $avail_roles['none' ] ) ) {
 
 			$class = '';
@@ -210,6 +233,8 @@
 
 			$name = __( 'No role' );
-			/* translators: User role name with count */
-			$name = sprintf( __('%1$s <span class="count">(%2$s)</span>'), $name, number_format_i18n( $avail_roles['none' ] ) );
+			if ( $count_users ) {
+				/* translators: User role name with count */
+				$name = sprintf( __('%1$s <span class="count">(%2$s)</span>'), $name, number_format_i18n( $avail_roles['none' ] ) );
+			}
 			$role_links['none'] = "<a href='" . esc_url( add_query_arg( 'role', 'none', $url ) ) . "'$class>$name</a>";
 
Index: /trunk/src/wp-includes/default-filters.php
===================================================================
--- /trunk/src/wp-includes/default-filters.php	(revision 41612)
+++ /trunk/src/wp-includes/default-filters.php	(revision 41613)
@@ -467,4 +467,9 @@
 add_action( 'init', 'wp_widgets_init', 1 );
 
+// User counts
+foreach ( array( 'user_register', 'deleted_user' ) as $action ){
+	add_action( $action, 'wp_update_active_user_count' );
+}
+
 // Admin Bar
 // Don't remove. Wrong way to disable.
Index: /trunk/src/wp-includes/functions.php
===================================================================
--- /trunk/src/wp-includes/functions.php	(revision 41612)
+++ /trunk/src/wp-includes/functions.php	(revision 41613)
@@ -5834,2 +5834,64 @@
 	), $email_change_email['message'], $email_change_email['headers'] );
 }
+
+/**
+ * Whether or not we have a large site, based on its number of users.
+ *
+ * The default criteria for a large site is more than 10,000 users.
+ *
+ * @since 4.9.0
+ *
+ * @return bool True if the site meets the criteria for large. False otherwise.
+ */
+function wp_is_large_user_count() {
+	$count = wp_get_active_user_count();
+
+	/**
+	 * Filters whether the site is considered large, based on its number of users.
+	 *
+	 * The default criteria for a large site is more than 10,000 users.
+	 *
+	 * @since 4.9.0
+	 *
+	 * @param bool $is_large_user_count Whether the site is considered large.
+	 * @param int  $count               The number of users on the site.
+	 */
+	return apply_filters( 'wp_is_large_user_count', $count > 10000, $count );
+}
+
+/**
+ * Update the active user count.
+ *
+ * @since 4.9.0
+ * @global wpdb $wpdb WordPress database abstraction object.
+ *
+ * @return int The active user count.
+ */
+function wp_update_active_user_count() {
+	global $wpdb;
+
+	$count = $wpdb->get_var( "
+		SELECT COUNT(ID) as c
+		FROM {$wpdb->users}
+	" );
+	$count=12345;
+	update_option( 'active_user_count', $count );
+
+	return (int) $count;
+}
+
+/**
+ * The number of active users.
+ *
+ * @since 4.9.0
+ *
+ * @return int The active user count.
+ */
+function wp_get_active_user_count() {
+	$count = get_option( 'active_user_count', false );
+
+	if ( false === $count ) {
+		$count = wp_update_active_user_count();
+	}
+	return (int) $count;
+}
Index: /trunk/src/wp-includes/ms-functions.php
===================================================================
--- /trunk/src/wp-includes/ms-functions.php	(revision 41612)
+++ /trunk/src/wp-includes/ms-functions.php	(revision 41613)
@@ -2554,4 +2554,9 @@
 	if ( 'users' == $using ) {
 		$count = get_user_count( $network_id );
+		$is_large = ( $count > 10000 );
+
+		/** This filter is documented in wp-includes/functions.php */
+		$is_large = apply_filters( 'wp_is_large_user_count', $is_large, $count );
+
 		/**
 		 * Filters whether the network is considered large.
@@ -2565,5 +2570,5 @@
 		 * @param int    $network_id       The ID of the network being checked.
 		 */
-		return apply_filters( 'wp_is_large_network', $count > 10000, 'users', $count, $network_id );
+		return apply_filters( 'wp_is_large_network', $is_large, 'users', $count, $network_id );
 	}
 
Index: /trunk/src/wp-includes/update.php
===================================================================
--- /trunk/src/wp-includes/update.php	(revision 41612)
+++ /trunk/src/wp-includes/update.php	(revision 41613)
@@ -79,6 +79,5 @@
 		$multisite_enabled = 1;
 	} else {
-		$user_count = count_users();
-		$user_count = $user_count['total_users'];
+		$user_count = wp_get_active_user_count();
 		$multisite_enabled = 0;
 		$num_blogs = 1;
Index: /trunk/tests/phpunit/tests/functions.php
===================================================================
--- /trunk/tests/phpunit/tests/functions.php	(revision 41612)
+++ /trunk/tests/phpunit/tests/functions.php	(revision 41613)
@@ -1161,3 +1161,57 @@
 		return $data;
 	}
+
+	/**
+	 * @ticket 38741
+	 */
+	public function test_wp_get_active_user_count() {
+		$user_count = wp_get_active_user_count();
+		$this->assertSame( $user_count, 1 );
+
+		// make twenty additional users to make 21 users
+		self::factory()->user->create_many( 20 );
+
+		$user_count = wp_get_active_user_count();
+		$this->assertSame( $user_count, 21 );
+	}
+
+	/**
+	 * @ticket 38741
+	 */
+	public function test_wp_get_active_user_count_caching() {
+		global $wpdb;
+
+		// Ensure we start with 1 user
+		$user_count = wp_get_active_user_count();
+		$this->assertSame( $user_count, 1 );
+
+		self::factory()->user->create();
+
+		delete_option( 'active_user_count' );
+
+		// Ensure we now have 2 users
+		$user_count = wp_get_active_user_count();
+		$this->assertSame( $user_count, 2 );
+
+		$queries = $wpdb->num_queries;
+
+		// Ensure that caching inside wp_get_active_user_count() works as expected
+		$user_count = wp_get_active_user_count();
+		$this->assertSame( $user_count, 2 );
+		$this->assertSame( $queries, $wpdb->num_queries );
+	}
+
+	/**
+	 * @ticket 38741
+	 */
+	public function test_wp_is_large_user_count() {
+		// set the 'active_user_count' value to over 10000 to emulate a large site
+		update_option( 'active_user_count', 10001 );
+		$user_count = wp_get_active_user_count();
+		$this->assertSame( $user_count, 10001 );
+		$this->assertTrue( wp_is_large_user_count() );
+
+		delete_option( 'active_user_count' );
+		$this->assertFalse( wp_is_large_user_count() );
+	}
 }
