Not_found

OCamlのコードを書くときにいつも迷っていることを書いてみます。超初心者質問。いい知恵ください。Not_foundの扱いです。
コンテナにデータがあった場合→データを使う、と無かった場合→データを新規に作る、で分岐する処理は頻出すると思います。

まず普通にif文。

if TABLE.mem key xs then
  let item = TABLE.find key xs in
  ...
else
  ...

これですと、探索を2回やってるわけで、遅そうです。
なので例外。

try
  let item = TABLE.find key xs in
  ... (*1*)
with Not_found -> ...

これですと、(*1*)部分に他にNot_foundを投げるような処理があった場合、例外をもみ消してしまいます。よろしくない。

なのでoption。

match (try Some (TABLE.find key xs) with Not_found -> None) with
| Some item ->
   ...
| None ->
   ...

これですと、Someのところでメモリアロケートが発生しています。こんなことで一時オブジェクトを作るのはGC的によろしくない。

例外の種類を差し替えるとか……。

try
  let item = try TABLE.find key xs with Not_found -> raise My_Not_found_2 in
  ... (*1*)
with My_Not_found_2 -> ...

……酷い無駄なコードな気がします。例外を投げたり受け止めたりというのは、普通に考えてメモリアロケートよりも重いわけで。

他の言語で行儀の悪いコードを書くなら、(*1*)でgotoしてとりあえずtryから出るようなことも可能なのですが、OCamlではそれはできません(ていうかOCaml文化以外の世界ならfindがNULLみたいな値を返して来ますよね、そもそも例外を使うような場面ではない)。一時オブジェクトを作ったりせずに、きれいにtryの範囲を限定するにはどうしたらいいでしょう。
え、一時オブジェクトを気にするな？いやまあそりゃあそうなんでしょうけど……。