The reason a stateful packet filter can perform better is that it usually has an easier job. Generally speaking, the state entries for ‘connections’ (which for UDPand other stateless protocols are really flows) are orderless and almost always unique. For example, for UDP and TCP , the tuple of source IP, source port, destination IP, and destination port uniquely identify a connection (possibly augmented with local context such as whether the packet is being received or sent, and on what network interface). When you have orderless and generally unique state entries like this, there are plenty of data structures that provide fast lookups for them, so it’s easy for the packet filter to find the state entry for a given packet (if it exists) and proceed from there.
By contrast, packet filtering rules are almost always ordered and not easily established as unique. A given packet often may potentially match multiple rules, and the order that you check rules for a match is usually semantically meaningful (often the firstmatching rule decides the packet’s fate). This means that you need to evaluate rules in order, or at least provide results that are the same as if you actually did that. In practice, even though you may have a lot of packet filtering rules, a given packet can only possibly match a few of them; however, transforming a general list of packet filtering rules into efficient data structures for rapid minimal matching is a non-trivial programming exercise and is rarely done automatically. This leaves packet filters to do a bunch of rule checking for every stateless packet.
(In theory you can hand-optimize your firewall rules. In practice the optimized versions may be much harder to understand and change, which isn’t necessarily a good tradeoff.)
The fly in this ointment is the question of what sort of traffic your packet filter actually sees. Common firewall implementations only establish state for successful connections (or flows); if the firewall rejects packets, they don’t create state. Thus, the more rejected traffic that your firewall sees compared to accepted traffic, the less state entries are helping you since every rejected packet always requires checking some or all of your firewall rules.
(But at least the accepted traffic gets a fast pass through the filter, which may be important even if you’re spending a lot of system resources on checking rules for packets that you reject.)