Is this happening with every file? 
If not please attacha pdf sample

I have been bitten by this issue on and off. I do not remember if with the same document I can get the good and bad behaviour. Usually I was bitten by the issue when I was too busy to debug it, and when I was not busy I could not reproduce it :-/

The following is in the source code:

/* We go through the tree linearly looking for the first page that
 * matches.  This is pretty inefficient.  We can do something neat with
 * a GtkTreeModelSort here to make it faster, if it turns out to be
 * slow.
 */

Yes. It does turn out to be slow - for example, grab 802.11-2012 from http://standards.ieee.org/about/get/802/802.11.html and scroll through it with the outline visible. It's much worse on the -2016 version, but sadly that's not available openly yet.

Note that the comment regarding GtkTreeModelSort is completely bogus - what's needed here isn't sorting, it's a reverse search going from page number to outline entry. A hashtable seems possible, but doesn't work because the outline will likely not have an entry for every page number, and fixing the problem of following properly in the outline while jumping to a page without an outline entry itself would be good.

A binary tree would likely be a good data structure for that, keeping a page number -> outline entry mapping for each first outline entry mapping on a page, and making the lookup go to the next smaller value if not found.

g_tree_search() can be used by passing as user_ptr a struct with the target page number to find, and an *output* pointer to the outline entry. That pointer can be filled on every g_tree_search() invocation, and then be used if g_tree_search() returned NULL. If it returns non-NULL, prefer that value of course.

Created attachment 350507 [details] [review]
ev-sidebar-links: Optimize reverse link lookup for a page

For large documents the linear search for the first link that is on a
certain page is really slow. Because of this scrolling becomes slow
whenever the page changes.

Replace the linear search with a search in a binary tree populated with
the first link on each page and the corresponding GtkTreePath. This way
a specialized binary tree lookup can be used to find the closest
matching link and select that in the treeview.

(In reply to Benjamin Berg from comment #5)
> Created attachment 350507 [details] [review] [review]
> ev-sidebar-links: Optimize reverse link lookup for a page

Tested on 3.22.1 - works great :)

Wow. Good job. It works good on master.

Review of attachment 350507 [details] [review]:

Thanks! it looks good to me, I have only a few minor comments.

::: shell/ev-sidebar-links.c
@@ +504,2 @@
 	/* Widget is not currently visible */
+	if (!gtk_widget_is_visible (GTK_WIDGET (sidebar_links)))

Why this change? is_visible only means it's marked as visible, not necessarily that it's visible, that's why mapped is used here, I think.

@@ +590,3 @@
+			       gpointer      data)
+{
+	EvSidebarLinks *sidebar_links = (data);

I know this is existing code but the () are useless here.

@@ +598,3 @@
+			    -1);
+
+	if (link) {

I would use an early return here if !link

@@ +601,3 @@
+		int page;
+		GtkTreePath *existing;
+		EvDocumentLinks *document_links = EV_DOCUMENT_LINKS (sidebar_links->priv->document);

you can use priv here instead of sidebar_links->priv.

@@ +608,3 @@
+		/* Only save the first link we find per page. */
+		existing = g_tree_lookup (priv->page_link_tree, GINT_TO_POINTER (page));
+		if (!existing)

We don't need the local variable

if (!g_tree_lookup())
        g_tree_insert()

I agree with all the style fixes.

The gtk_widget_get_mapped still returns TRUE if the Overview is selected but the sidebar is hidden in evince. gtk_widget_is_visible does not seem to do it in this case. So it seems like a widget can still be mapped while being invisible

tbh. I am not sure about the semantics right now, but is_visible() should is safe and catches a case that was not caught before.

Oh, is_visible tests the whole widget hierarchy, not only the widget itself (which would be get_visible).

Created attachment 350727 [details] [review]
ev-sidebar-links: Optimize reverse link lookup for a page

For large documents the linear search for the first link that is on a
certain page is really slow. Because of this scrolling becomes slow
whenever the page changes.

Replace the linear search with a search in a binary tree populated with
the first link on each page and the corresponding GtkTreePath. This way
a specialized binary tree lookup can be used to find the closest
matching link and select that in the treeview.

Review of attachment 350727 [details] [review]:

Excellent! I've just pushed it, thank you!

The patch applies as-is to older versions, I've tested it on 3.22 for example - perhaps you'd be willing to also put it at least on 3.24 or perhaps also 3.22?

I know a number of people working on wifi who really have this problem with the 802.11-2016 spec (basically, evince isn't usable to view it at all), and having it deployed earlier than 3.26 (September?) would be really nice.

Thanks!

(In reply to Johannes Berg from comment #13)
> The patch applies as-is to older versions, I've tested it on 3.22 for
> example - perhaps you'd be willing to also put it at least on 3.24 or
> perhaps also 3.22?
> 
> I know a number of people working on wifi who really have this problem with
> the 802.11-2016 spec (basically, evince isn't usable to view it at all), and
> having it deployed earlier than 3.26 (September?) would be really nice.
> 
> Thanks!

Sure, I've just backported it to 3.24 branch

Thanks!