Does it not inherently punish small payments? Say, if I send 100 mSAT it will always be failed due to base fee alone (I guess).

That is a good point, that I was discussing with @dpad85. Do we really want to allow sending 100 msat if it costs the user 10 sats?

Well that's exactly what I did for now by using a parabolic fee function dependent on payment sum.

a parabolic fee function? what's that?

something like this:

def logOfBase(base: Long, sum: Long) = math.log(sum) / math.log(base)
def maxAcceptableLNFee(msat: Long) = msat / math.pow(logOfBase(100, msat), 4)
def feePerCent(msat: Long) = maxAcceptableLNFee(msat: Long) / msat

Here, 100 mSAT is selected as "inflection point" meaning a max acceptable fee size would be 100% for 100 mSAT. It will quickly grow to 1600% (160 mSAT) as payment goes to 10 mSAT and quickly falls to 1% as payment goes to 1000000 mSAT.

And still this only covers proportional part, base fee should be taken care of differently I guess, maybe by calculating a mean basefee across the graph with outliers excluded (for example outlier basefees could be those beyond 2nd standard deviation) and then multiplied by number of hops.

Maybe I'm complicating everything a lot though!

The way I see it, it is never acceptable to pay 100% fees, and if there is no route available on the network with low enough fees, then the payment just doesn't makes sense economically (*).

Just because LN is technically able to relay sub-satoshi payments doesn't mean that it is economically viable and that we should encourage it at all cost. I think this is something the market will decide (same applies for on-chain payments).

The definition of what is the minimum practical payment on LN will be given by node operators, not by people sending or receiving payments (but those can also be node operators).

(*) Note that you still can do it with this PR by setting a very high maxPaymentFee.