Using OpenGL in blender python
As you have noticed, drawing bgl is relative easy. For trivial stuff many settle for immediate mode, because the overhead in their drawing routine is never noticed (either a really fast processor, or simply minimal drawing instructions).

As soon as you crank up the amount of geometry and complexity of the drawing call, you will need to think about optimizations and perhaps use a DisplayList. Optimize the code you were using in immediate mode first. Use timers and reproducible geometric inputs to see what kind of effect your code modifications have and figure out which parts take up the most time overal and concentrate on those, profiling helps.

A DisplayList isn't magically going to make your fresh bgl drawing faster.


You already noticed that using the push / pop matrix for 3 vertices can introduce more overhead than calculating them directly.
a .co  is already a Vector, it doesn't need to be recast as a Vector()
I'd try some counter intuitive things like pre-calculating the coordinates for all polygons you intend to draw, then for-loop through them inside GL_TRIANGLES where each 3 new vertices pushed is part of a new Tri.
Consider numpy! initial filling of arrays may be the bottle neck, after that you can get a lot of processing done very fast with the right constructs. (becomes off-topic for BSE)




50k plus edges, in your program translates to 50k polygons with 150k vertices, that's a lot of geometry to update/recalcuate with python and bgl at a high frame-rate. 


It may be worth considering splitting it into subsets, if not all data needs to be updated
If it makes sense, show only a sampling of all your points, show more samples in the area you are editing, and less or no samples from beyond it.
If it's not visible, does it need to be calculated.
does it need to be 3d? it's easy to convert view3d 3d coordinates to 2d screen coordinates, and drop edges if they don't meet some criteria like:


the length of the edge on-screen is below a set amount of pixels, don't calculate draw arrow, don't draw it.
are both (or just one) coordinates of the edge visible, decide based on this whether you need to draw it.

only consider selected edges (this will include the active edge).




Alternatives to bgl

Mesh

For Sverchok we found it was worth experimenting with a non bgl way of displaying mesh data, by generating a Mesh object and let Blender take care of the Drawing! Such a Mesh object can either be wiped and refilled between updates or you can use a foreach_set('co', flatlist) when the geometry of the existing mesh has the same amount of coordinates as the geometry you're trying to replace it with. It might be worth reading the code we settled on: nodes/basic_view/viewer_bmesh_mk2.py  -- there's no guarantee this this will be any faster, but it does sidestep home-grown bgl code.

DupliVerts + rotation

It is possible to make a secondary mesh with only the points where these arrows are supposed to appear, and then assign the vertices of the secondary mesh each a custom normal by doing v.normal = orientation. The duplicated Object will then rotate to point in the orientation passed to the normals. Example code: https://gist.github.com/zeffii/d61a4963e6c093dda52b




drawback is that if you go into Edit Mode for the duplivert mesh, the normals will reset. (but you probably don't even need to go directly into edit mode for that mesh..)  
it is possible to use foreach_set('normal', flatlist) on the data.vertices collection which is quite fast.