P-spline represents an unknown f(x) with uniform B-splines on equidistant knots and penalize it with a simple difference matrix for smoothness. But for non-uniform B-splines on non-uniform knots, such difference penalty makes no sense, so the conventional derivative penalty $\int f^{(m)}(x)^2 dx$ is hitherto the only choice. We now lift this restriction by deriving a general difference penalty for non-uniform B-splines, leading to the general P-spline. We also establish an explicit link between derivative and general difference penalties, so that their connection is better understood. Simulations show that both P-spline variants have very close MSE performance in general. But in practice, one can yield a more satisfactory fit than the other. For example, the bone mineral content (BMC) longitudinal data favor general P-spline, while the fossil shell data favor standard P-spline. We therefore believe that both variants are useful tools for practical modeling. To implement general P-spline, we provide R packages gps and gps.mgcv. The latter creates a new "gps" smooth class for mgcv, so that a general P-spline can be specified like s(x, bs = "gps") in a model formula and estimated in the framework of generalized additive models.