1use crate::http::{HttpError, Request, Transport};
8use futures_util::future::try_join_all;
9use serde::Serialize;
10use serde_json::{Map, Value, json};
11use sha2::{Digest, Sha256};
12use std::{fmt::Write as _, time::Duration};
13use tokio::io::{AsyncBufReadExt, AsyncReadExt, BufReader};
14use tokio_util::sync::CancellationToken;
15
16pub const FIXTURE_VERSION: u32 = 1;
17
18const MAX_LINE_BYTES: usize = 64 * 1024;
19const MAX_BODY_BYTES: usize = 16 * 1024 * 1024;
20const REQUEST_TIMEOUT: Duration = Duration::from_secs(600);
21const MAX_COUNT: u64 = 1_000_000_000;
22const MAX_MILLIS: f64 = 1.0e10;
23const MAX_NANOS: u64 = 10_000_000_000_000_000;
24const MAX_ERROR_CHARS: usize = 256;
25const SEED: u64 = 42;
26
27const SHORT_TEXT: &str = "You are taking part in a fixed performance benchmark. \
28Reply with exactly five numbered lines. Each line must name one common garden \
29vegetable followed by a single short sentence describing its colour. Do not add \
30any introduction, conclusion, or extra commentary.\n";
31
32macro_rules! long_paragraph {
33 () => {
34 "The keeper of the harbour light kept a ledger of small and ordinary things. \
35Each morning she wrote down the direction of the wind, the colour of the water near \
36the breakwater, the number of gulls resting on the old stone pier, and whether the \
37fishing boats had left before or after the bell in the square rang six times. She did \
38not believe the ledger was important to anyone else, yet she kept it with great care, \
39because a careful record of quiet days made the unusual days easier to recognise. When \
40the fog arrived early, she compared it with earlier pages and noticed patterns in the \
41tides, the temperature of the air, and the way the lamp oil thickened in the cold. Over \
42many seasons the pages became a patient map of the coast, drawn not with lines and \
43coordinates but with plain sentences, steady handwriting, and the habit of looking at \
44the same horizon every single day without growing tired of it.\n\n"
45 };
46}
47
48const LONG_TEXT: &str = concat!(
49 "You are taking part in a fixed performance benchmark. Read the following \
50passage carefully. Afterwards, write a numbered list of exactly five short \
51observations about the habits of the keeper described in the passage. Do not \
52quote the passage and do not add any introduction or conclusion.\n\n",
53 "Section 1. ",
54 long_paragraph!(),
55 "Section 2. ",
56 long_paragraph!(),
57 "Section 3. ",
58 long_paragraph!(),
59 "Section 4. ",
60 long_paragraph!(),
61 "Section 5. ",
62 long_paragraph!(),
63 "Section 6. ",
64 long_paragraph!(),
65 "Section 7. ",
66 long_paragraph!(),
67 "Section 8. ",
68 long_paragraph!(),
69 "Now write the five numbered observations.\n",
70);
71
72#[derive(Debug, thiserror::Error)]
73pub enum BenchError {
74 #[error("benchmarking is not supported for backend `{0}`")]
75 Unsupported(String),
76 #[error("invalid benchmark options: {0}")]
77 InvalidOptions(&'static str),
78 #[error("invalid benchmark request")]
79 InvalidRequest,
80 #[error("local runtime HTTP {0}")]
81 Status(u16),
82 #[error("local runtime transport failed")]
83 Transport,
84 #[error("local runtime response exceeds limit")]
85 Limit,
86 #[error("invalid local runtime benchmark response")]
87 Response,
88 #[error("local runtime reported an error: {0}")]
89 Runtime(String),
90 #[error("benchmark cancelled")]
91 Cancelled,
92 #[error("benchmark request timed out")]
93 Timeout,
94}
95
96impl From<HttpError> for BenchError {
97 fn from(error: HttpError) -> Self {
98 match error {
99 HttpError::Invalid => Self::InvalidRequest,
100 HttpError::Status(status) => Self::Status(status),
101 HttpError::Transport => Self::Transport,
102 HttpError::Limit => Self::Limit,
103 HttpError::Response => Self::Response,
104 HttpError::Cancelled => Self::Cancelled,
105 HttpError::Timeout => Self::Timeout,
106 }
107 }
108}
109
110#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Serialize)]
111#[serde(rename_all = "lowercase")]
112pub enum Fixture {
113 #[default]
114 Short,
115 Long,
116}
117
118impl Fixture {
119 pub fn id(self) -> &'static str {
120 match self {
121 Self::Short => "short",
122 Self::Long => "long",
123 }
124 }
125 pub fn text(self) -> &'static str {
126 match self {
127 Self::Short => SHORT_TEXT,
128 Self::Long => LONG_TEXT,
129 }
130 }
131 pub fn sha256(self) -> String {
132 hex(&Sha256::digest(self.text().as_bytes()))
133 }
134}
135
136fn hex(bytes: &[u8]) -> String {
137 bytes
138 .iter()
139 .fold(String::with_capacity(64), |mut out, byte| {
140 let _ = write!(out, "{byte:02x}");
141 out
142 })
143}
144
145#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
146#[serde(rename_all = "lowercase")]
147pub enum Protocol {
148 Ollama,
149 #[serde(rename = "llamacpp")]
150 LlamaCpp,
151}
152
153impl Protocol {
154 pub fn for_backend(backend: &str) -> Result<Self, BenchError> {
155 match backend {
156 "ollama" => Ok(Self::Ollama),
157 "llamacpp" | "bitnet" => Ok(Self::LlamaCpp),
158 other => Err(BenchError::Unsupported(sanitize(other, 64))),
159 }
160 }
161 fn label(self) -> &'static str {
162 match self {
163 Self::Ollama => "Ollama",
164 Self::LlamaCpp => "llama.cpp",
165 }
166 }
167}
168
169#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
170#[serde(rename_all = "camelCase")]
171pub struct BenchOptions {
172 pub iterations: u8,
173 pub warmup: u8,
174 pub output_tokens: u32,
175 pub concurrency: u8,
176 pub fixture: Fixture,
177}
178
179impl Default for BenchOptions {
180 fn default() -> Self {
181 Self {
182 iterations: 5,
183 warmup: 1,
184 output_tokens: 128,
185 concurrency: 1,
186 fixture: Fixture::Short,
187 }
188 }
189}
190
191impl BenchOptions {
192 pub fn validate(&self) -> Result<(), BenchError> {
193 if !(1..=20).contains(&self.iterations) {
194 return Err(BenchError::InvalidOptions("iterations must be 1..=20"));
195 }
196 if self.warmup > 5 {
197 return Err(BenchError::InvalidOptions("warmup must be 0..=5"));
198 }
199 if !(16..=2048).contains(&self.output_tokens) {
200 return Err(BenchError::InvalidOptions(
201 "output tokens must be 16..=2048",
202 ));
203 }
204 if !(1..=16).contains(&self.concurrency) {
205 return Err(BenchError::InvalidOptions("concurrency must be 1..=16"));
206 }
207 Ok(())
208 }
209}
210
211pub trait Clock: Send + Sync {
213 fn now(&self) -> Duration;
214}
215
216pub struct SystemClock {
217 origin: std::time::Instant,
218}
219
220impl SystemClock {
221 pub fn new() -> Self {
222 Self {
223 origin: std::time::Instant::now(),
224 }
225 }
226}
227
228impl Default for SystemClock {
229 fn default() -> Self {
230 Self::new()
231 }
232}
233
234impl Clock for SystemClock {
235 fn now(&self) -> Duration {
236 self.origin.elapsed()
237 }
238}
239
240#[derive(Debug, Clone, PartialEq, Serialize)]
241#[serde(rename_all = "camelCase")]
242pub struct RunSample {
243 pub ttft_ms: Option<f64>,
245 pub wall_ms: f64,
247 pub prompt_tokens: Option<u64>,
248 pub generated_tokens: Option<u64>,
249 pub prefill_tps: Option<f64>,
250 pub decode_tps: Option<f64>,
251 pub draft_tokens: Option<u64>,
252 pub draft_accepted: Option<u64>,
253}
254
255#[derive(Debug, Clone, PartialEq, Serialize)]
256#[serde(rename_all = "camelCase")]
257pub struct Stat {
258 pub median: f64,
259 pub p10: f64,
260 pub p90: f64,
261 pub n: usize,
262}
263
264impl Stat {
265 pub fn from_samples(values: &[f64]) -> Option<Self> {
268 let mut sorted: Vec<f64> = values.iter().copied().filter(|v| v.is_finite()).collect();
269 if sorted.is_empty() {
270 return None;
271 }
272 sorted.sort_by(f64::total_cmp);
273 let n = sorted.len();
274 let median = if n % 2 == 1 {
275 sorted[n / 2]
276 } else {
277 (sorted[n / 2 - 1] + sorted[n / 2]) / 2.0
278 };
279 Some(Self {
280 median,
281 p10: nearest_rank(&sorted, 10),
282 p90: nearest_rank(&sorted, 90),
283 n,
284 })
285 }
286}
287
288fn nearest_rank(sorted: &[f64], percent: usize) -> f64 {
289 let n = sorted.len();
290 let rank = (percent * n).div_ceil(100);
291 sorted[rank.saturating_sub(1).min(n - 1)]
292}
293
294#[derive(Debug, Clone, PartialEq, Serialize)]
295#[serde(rename_all = "camelCase")]
296pub struct FixtureInfo {
297 pub id: &'static str,
298 pub version: u32,
299 pub sha256: String,
300}
301
302#[derive(Debug, Clone, PartialEq, Serialize)]
303#[serde(rename_all = "camelCase")]
304pub struct BenchReport {
305 pub protocol: Protocol,
306 pub model: String,
307 pub fixture: FixtureInfo,
308 pub options: BenchOptions,
309 pub ttft_ms: Option<Stat>,
311 pub prefill_tps: Option<Stat>,
313 pub decode_tps: Option<Stat>,
315 pub draft_acceptance: Option<f64>,
317 pub aggregate_decode_tps: Option<Stat>,
319 pub samples: Vec<RunSample>,
320}
321
322fn sanitize(value: &str, limit: usize) -> String {
323 value
324 .chars()
325 .filter(|c| !c.is_control())
326 .take(limit)
327 .collect()
328}
329
330fn valid_model(model: &str) -> bool {
331 !model.is_empty()
332 && model.len() <= 256
333 && !model.chars().any(|c| c.is_control() || c.is_whitespace())
334}
335
336fn nonce(round: u32, slot: u8) -> String {
337 format!("Benchmark request {round}-{slot}.\n")
338}
339
340fn request_body(
341 protocol: Protocol,
342 model: &str,
343 prompt: &str,
344 options: &BenchOptions,
345) -> (&'static str, Value) {
346 match protocol {
347 Protocol::Ollama => (
348 "/api/generate",
349 json!({
350 "model": model,
351 "prompt": prompt,
352 "stream": true,
353 "options": {
354 "num_predict": options.output_tokens,
355 "temperature": 0,
356 "seed": SEED,
357 },
358 }),
359 ),
360 Protocol::LlamaCpp => (
361 "/completion",
362 json!({
363 "prompt": prompt,
364 "n_predict": options.output_tokens,
365 "stream": true,
366 "cache_prompt": false,
367 "temperature": 0,
368 "seed": SEED,
369 }),
370 ),
371 }
372}
373
374fn count(object: &Map<String, Value>, key: &str) -> Result<Option<u64>, BenchError> {
375 match object.get(key) {
376 None | Some(Value::Null) => Ok(None),
377 Some(value) => value
378 .as_u64()
379 .filter(|n| *n <= MAX_COUNT)
380 .map(Some)
381 .ok_or(BenchError::Response),
382 }
383}
384
385fn nanos(object: &Map<String, Value>, key: &str) -> Result<Option<f64>, BenchError> {
386 match object.get(key) {
387 None | Some(Value::Null) => Ok(None),
388 Some(value) => value
389 .as_u64()
390 .filter(|n| *n <= MAX_NANOS)
391 .map(|n| Some(n as f64 / 1.0e9))
392 .ok_or(BenchError::Response),
393 }
394}
395
396fn millis(object: &Map<String, Value>, key: &str) -> Result<Option<f64>, BenchError> {
397 match object.get(key) {
398 None | Some(Value::Null) => Ok(None),
399 Some(value) => value
400 .as_f64()
401 .filter(|ms| ms.is_finite() && (0.0..=MAX_MILLIS).contains(ms))
402 .map(|ms| Some(ms / 1000.0))
403 .ok_or(BenchError::Response),
404 }
405}
406
407fn rate(tokens: Option<u64>, seconds: Option<f64>) -> Option<f64> {
408 let (tokens, seconds) = (tokens?, seconds?);
409 if tokens == 0 || !(seconds.is_finite() && seconds > 0.0) {
410 return None;
411 }
412 Some(tokens as f64 / seconds).filter(|tps| tps.is_finite() && *tps > 0.0)
413}
414
415#[derive(Default)]
416struct Counters {
417 prompt_tokens: Option<u64>,
418 generated_tokens: Option<u64>,
419 prefill_tps: Option<f64>,
420 decode_tps: Option<f64>,
421 draft_tokens: Option<u64>,
422 draft_accepted: Option<u64>,
423}
424
425enum Event {
426 Skip,
427 Content,
428 Final(Counters),
429}
430
431fn runtime_error(value: &Value) -> Option<BenchError> {
432 let error = value.get("error")?;
433 let message = match error {
434 Value::Null => return None,
435 Value::String(text) => text.as_str(),
436 Value::Object(object) => object
437 .get("message")
438 .and_then(Value::as_str)
439 .unwrap_or("unknown error"),
440 _ => "unknown error",
441 };
442 Some(BenchError::Runtime(sanitize(message, MAX_ERROR_CHARS)))
443}
444
445fn non_empty_str(object: &Map<String, Value>, key: &str) -> Result<bool, BenchError> {
446 match object.get(key) {
447 None | Some(Value::Null) => Ok(false),
448 Some(Value::String(text)) => Ok(!text.is_empty()),
449 Some(_) => Err(BenchError::Response),
450 }
451}
452
453fn flag(object: &Map<String, Value>, key: &str) -> Result<bool, BenchError> {
454 match object.get(key) {
455 None | Some(Value::Null) => Ok(false),
456 Some(Value::Bool(value)) => Ok(*value),
457 Some(_) => Err(BenchError::Response),
458 }
459}
460
461fn ollama_event(line: &[u8]) -> Result<Event, BenchError> {
462 let value: Value = serde_json::from_slice(line).map_err(|_| BenchError::Response)?;
463 if let Some(error) = runtime_error(&value) {
464 return Err(error);
465 }
466 let object = value.as_object().ok_or(BenchError::Response)?;
467 if flag(object, "done")? {
468 let prompt_tokens = count(object, "prompt_eval_count")?;
469 let generated_tokens = count(object, "eval_count")?;
470 return Ok(Event::Final(Counters {
471 prompt_tokens,
472 generated_tokens,
473 prefill_tps: rate(prompt_tokens, nanos(object, "prompt_eval_duration")?),
474 decode_tps: rate(generated_tokens, nanos(object, "eval_duration")?),
475 draft_tokens: None,
476 draft_accepted: None,
477 }));
478 }
479 if non_empty_str(object, "response")? || non_empty_str(object, "thinking")? {
480 return Ok(Event::Content);
481 }
482 Ok(Event::Skip)
483}
484
485fn llamacpp_event(line: &[u8]) -> Result<Event, BenchError> {
486 let Some(payload) = line.strip_prefix(b"data:") else {
487 return Ok(Event::Skip);
489 };
490 let payload = payload.strip_prefix(b" ").unwrap_or(payload);
491 if payload == b"[DONE]" {
492 return Ok(Event::Skip);
493 }
494 let value: Value = serde_json::from_slice(payload).map_err(|_| BenchError::Response)?;
495 if let Some(error) = runtime_error(&value) {
496 return Err(error);
497 }
498 let object = value.as_object().ok_or(BenchError::Response)?;
499 if flag(object, "stop")? {
500 let Some(timings) = object.get("timings").filter(|v| !v.is_null()) else {
501 return Ok(Event::Final(Counters::default()));
502 };
503 let timings = timings.as_object().ok_or(BenchError::Response)?;
504 let prompt_tokens = count(timings, "prompt_n")?;
505 let generated_tokens = count(timings, "predicted_n")?;
506 let draft_tokens = count(timings, "draft_n")?;
507 let draft_accepted = count(timings, "draft_n_accepted")?;
508 if let (Some(drafted), Some(accepted)) = (draft_tokens, draft_accepted)
509 && accepted > drafted
510 {
511 return Err(BenchError::Response);
512 }
513 return Ok(Event::Final(Counters {
514 prompt_tokens,
515 generated_tokens,
516 prefill_tps: rate(prompt_tokens, millis(timings, "prompt_ms")?),
517 decode_tps: rate(generated_tokens, millis(timings, "predicted_ms")?),
518 draft_tokens,
519 draft_accepted,
520 }));
521 }
522 if non_empty_str(object, "content")? {
523 return Ok(Event::Content);
524 }
525 Ok(Event::Skip)
526}
527
528fn elapsed_ms(clock: &dyn Clock, start: Duration) -> f64 {
529 clock.now().saturating_sub(start).as_secs_f64() * 1000.0
530}
531
532#[allow(clippy::too_many_arguments)]
533async fn one_request(
534 transport: &dyn Transport,
535 clock: &dyn Clock,
536 endpoint: &str,
537 model: &str,
538 protocol: Protocol,
539 options: &BenchOptions,
540 round: u32,
541 slot: u8,
542 cancel: &CancellationToken,
543) -> Result<RunSample, BenchError> {
544 let prompt = format!("{}{}", nonce(round, slot), options.fixture.text());
545 let (path, body) = request_body(protocol, model, &prompt, options);
546 let request = Request::new(endpoint, path, Some(body), None)?;
547 let parse = match protocol {
548 Protocol::Ollama => ollama_event,
549 Protocol::LlamaCpp => llamacpp_event,
550 };
551 let operation = async {
552 let start = clock.now();
553 let response = transport.send(request).await?;
554 if !(200..300).contains(&response.status) {
555 return Err(BenchError::Status(response.status));
556 }
557 let mut reader = BufReader::new(response.body);
558 let mut total = 0usize;
559 let mut ttft_ms = None;
560 loop {
561 let mut line = Vec::new();
562 let read = (&mut reader)
563 .take(MAX_LINE_BYTES as u64 + 1)
564 .read_until(b'\n', &mut line)
565 .await
566 .map_err(|_| BenchError::Transport)?;
567 if read == 0 {
568 return Err(BenchError::Response);
570 }
571 total += read;
572 if read > MAX_LINE_BYTES || total > MAX_BODY_BYTES {
573 return Err(BenchError::Limit);
574 }
575 let trimmed = line.trim_ascii();
576 if trimmed.is_empty() {
577 continue;
578 }
579 match parse(trimmed)? {
580 Event::Skip => {}
581 Event::Content => {
582 if ttft_ms.is_none() {
583 ttft_ms = Some(elapsed_ms(clock, start));
584 }
585 }
586 Event::Final(counters) => {
587 return Ok(RunSample {
588 ttft_ms,
589 wall_ms: elapsed_ms(clock, start),
590 prompt_tokens: counters.prompt_tokens,
591 generated_tokens: counters.generated_tokens,
592 prefill_tps: counters.prefill_tps,
593 decode_tps: counters.decode_tps,
594 draft_tokens: counters.draft_tokens,
595 draft_accepted: counters.draft_accepted,
596 });
597 }
598 }
599 }
600 };
601 tokio::select! {
602 biased;
603 _ = cancel.cancelled() => Err(BenchError::Cancelled),
604 result = tokio::time::timeout(REQUEST_TIMEOUT, operation) => {
605 result.map_err(|_| BenchError::Timeout)?
606 }
607 }
608}
609
610pub async fn run(
614 transport: &dyn Transport,
615 clock: &dyn Clock,
616 endpoint: &str,
617 model: &str,
618 protocol: Protocol,
619 options: &BenchOptions,
620 cancel: &CancellationToken,
621) -> Result<BenchReport, BenchError> {
622 options.validate()?;
623 if !valid_model(model) {
624 return Err(BenchError::InvalidRequest);
625 }
626 Request::new(endpoint, "/", None, None)?;
627 let rounds = u32::from(options.warmup) + u32::from(options.iterations);
628 let mut samples =
629 Vec::with_capacity(usize::from(options.iterations) * usize::from(options.concurrency));
630 let mut round_rates = Vec::new();
631 for round in 0..rounds {
632 if cancel.is_cancelled() {
633 return Err(BenchError::Cancelled);
634 }
635 let round_start = clock.now();
636 let batch = try_join_all((0..options.concurrency).map(|slot| {
637 one_request(
638 transport, clock, endpoint, model, protocol, options, round, slot, cancel,
639 )
640 }))
641 .await?;
642 let round_seconds = clock.now().saturating_sub(round_start).as_secs_f64();
643 if round < u32::from(options.warmup) {
644 continue;
645 }
646 if options.concurrency > 1 {
647 let generated: Option<u64> = batch.iter().map(|s| s.generated_tokens).sum();
648 if let Some(rate) = rate(generated, Some(round_seconds)) {
649 round_rates.push(rate);
650 }
651 }
652 samples.extend(batch);
653 }
654 let collect = |pick: fn(&RunSample) -> Option<f64>| {
655 Stat::from_samples(&samples.iter().filter_map(pick).collect::<Vec<_>>())
656 };
657 let (drafted, accepted) = samples
658 .iter()
659 .filter_map(|s| Some((s.draft_tokens?, s.draft_accepted?)))
660 .fold((0u64, 0u64), |(d, a), (sd, sa)| {
661 (d.saturating_add(sd), a.saturating_add(sa))
662 });
663 let draft_acceptance = (drafted > 0).then(|| accepted as f64 / drafted as f64);
664 Ok(BenchReport {
665 protocol,
666 model: model.to_owned(),
667 fixture: FixtureInfo {
668 id: options.fixture.id(),
669 version: FIXTURE_VERSION,
670 sha256: options.fixture.sha256(),
671 },
672 options: options.clone(),
673 ttft_ms: collect(|s| s.ttft_ms),
674 prefill_tps: collect(|s| s.prefill_tps),
675 decode_tps: collect(|s| s.decode_tps),
676 draft_acceptance,
677 aggregate_decode_tps: Stat::from_samples(&round_rates),
678 samples,
679 })
680}
681
682fn stat_line(out: &mut String, label: &str, stat: Option<&Stat>, unit: &str, missing: &str) {
683 let _ = match stat {
684 Some(stat) => writeln!(
685 out,
686 "{label:<22} {:.1} {unit} (p10 {:.1} · p90 {:.1}, n={})",
687 stat.median, stat.p10, stat.p90, stat.n
688 ),
689 None => writeln!(out, "{label:<22} unknown ({missing})"),
690 };
691}
692
693pub fn render_text(report: &BenchReport) -> String {
694 let mut out = String::new();
695 let options = &report.options;
696 let _ = writeln!(out, "Runtime: {}", report.protocol.label());
697 let _ = writeln!(out, "Model: {}", sanitize(&report.model, 256));
698 let _ = writeln!(
699 out,
700 "Fixture: {} v{} (sha256 {})",
701 report.fixture.id,
702 report.fixture.version,
703 sanitize(&report.fixture.sha256, 64)
704 );
705 let _ = writeln!(
706 out,
707 "Runs: {} measured after {} warmup · {} output tokens max · concurrency {}",
708 options.iterations, options.warmup, options.output_tokens, options.concurrency
709 );
710 out.push('\n');
711 stat_line(
712 &mut out,
713 "TTFT (wall clock):",
714 report.ttft_ms.as_ref(),
715 "ms",
716 "runtime did not stream content",
717 );
718 stat_line(
719 &mut out,
720 "Prefill (runtime):",
721 report.prefill_tps.as_ref(),
722 "tok/s",
723 "runtime did not report prompt timing",
724 );
725 stat_line(
726 &mut out,
727 "Decode (runtime):",
728 report.decode_tps.as_ref(),
729 "tok/s",
730 "runtime did not report generation timing",
731 );
732 let _ = match report.draft_acceptance {
733 Some(ratio) => writeln!(out, "{:<22} {:.1}%", "Draft acceptance:", ratio * 100.0),
734 None => writeln!(
735 out,
736 "{:<22} unknown (runtime did not report speculative draft counters)",
737 "Draft acceptance:"
738 ),
739 };
740 if options.concurrency > 1 {
741 stat_line(
742 &mut out,
743 "Aggregate (wall clock):",
744 report.aggregate_decode_tps.as_ref(),
745 "tok/s",
746 "runtime did not report generated token counts",
747 );
748 }
749 out
750}