Many software systems today are configurable, offering customization of functionality byfeature selection. Understanding how performance varies in terms of featureselection is key for selecting appropriate configurations that meet a set ofgiven requirements. Due to a huge configuration space and the possibly highcost of performance measurement, it is usually not feasible to explore theentire configuration space of a configurable system exhaustively. It is thus amajor challenge to accurately predict performance based on a small sample ofmeasured system variants. To address this challenge, we propose adata-efficient learning approach, called DECART, that combines severaltechniques of machine learning and statistics for performance prediction ofconfigurable systems. DECART builds, validates, and determines a predictionmodel based on an available sample of measured system variants. Empiricalresults on 10 real-world configurable systems demonstrate the effectiveness andpracticality of DECART. In particular, DECART achieves a prediction accuracy of90% or higher based on a small sample, whose size is linear in the number offeatures. In addition, we propose a sample quality metric and introduce aquantitative analysis of the quality of a sample for performance prediction.