Optimizing jQuery list filtering
The root of the problem is you have ~3100 items in the page. This could be simplified by using pagination. If this is a traditional page, page the output. If this is a webapp, you may have all ~3100 in memory, but don't render it all. Besides, there's no point rendering ~3100 items unfiltered anyways. Who scrolls through ~3100 items?

Granted that you don't have any other option but to render it all and filter on the spot, the next problem with your code is that it generates a lot of jQuery objects. Every time you call the $() function, a jQuery object is generated.

// Here, the $(v)
var list = $.makeArray(lis.map(function(k, v) {
    return $(v).text().toLowerCase();
}));

// Here, the $(value)
lis.each(function(index, value) {
    if (list[index].indexOf(userInput) &gt;= 0) {
        count++;
        $(value).show();
    } else {
        $(value).hide();
    }
});


One way to avoid this is to collectively do the show and hide instead of doing it per item. In the following code, it gathers all elements to show and to hide, wraps both arrays in jQuery and calls show and hide. 

var toShow = [];
var toHide = [];
lis.each(function(index, value){
  if (list[index].indexOf(userInput) &gt;= 0) {
    toShow.push(this);
  } else {
    toHide.push(this);
  }
});

$(toShow).show();
$(toHide).hide();


Notice that I only called $() twice, and .show() and .hide() once instead of per item. We just avoided creating ~3100 jQuery objects!

Another way to improve this code is to use native operations whenever possible. It's not that they're faster by themselves, but you reduce reliance to jQuery, avoiding creation of jQuery objects when ordinary arrays would have sufficed.

var list = $.makeArray(lis.map(function(k, v) {
  return $(v).text().toLowerCase();
}));


This code above could have been simplified into

var list = lis.get().map(function(element){
  return (element.innerText || element.textContent).toLowerCase();
});


In the "improved version", notice that 1) it uses a native array instead of jQuery in the first place, allowing the use of the native array.map and 2) it doesn't call $() in the callback at all. We just avoided ~3100 jQuery objects again!

Now back to your toggling code, I think I see an update you did before my answer by adding/removing classes. That's a good move because 1) styling should be done in CSS and 2) show and hide uses inline styles. They are hard to override from a stylesheet. The only way you could is to use !important which you should generally avoid.

As for your question about removal vs hiding, I'd say go for hiding. As far as I know, removals are slow. This is even worse when there are stuff attached to the elements in question. For instance, removing an element with jQuery handlers attached. jQuery has to clean them up, remove references to data and handlers etc. If removals aren't done properly, you could have a lot of lingering things in memory.